4 Presentations

• 
  10:30 AM - 10:55 AM

  A k-medians model for semi-supervised clustering

  • Rodrigo Randel, presenter, École Polytechnique de Montréal
  • Daniel Aloise, Polytechnique Montréal
  • Pierre Hansen, HEC Montréal
  • Nenad Mladenovic, Mathematical Institute SANU

  Clustering is a powerful tool for automated analysis of data. It addresses the following general problem: given a set of entities, find subsets, or clusters, which are homogeneous and/or well separated. The biggest challenge of data clustering is to find a criterion to present good separation of data into homogeneous groups, so that these groups bring useful information to the user. To mitigate the importance of this decision, it is suggested that the expert could provide some a priori information about the data set. Clustering under this assumption is called semi-supervised clustering. This work explores semi-supervised clustering using the k-medians model. Results shows that (i) the model presents classification accuracy compared to that of the typical k-means approach, and (ii) it allows to efficiently explore dual information in order to guide cluster analysis.

• 
  10:55 AM - 11:20 AM

  ANNULÉ / CANCELED: The Carousel Scheduling Problem

  • Bruno Pessoa, Universidade Federal da Paraíba
  • Lucidio Cabral, Universidade Federal da Paraíba
  • Daniel Aloise, presenter, Polytechnique Montréal
  • Lucidio Cabral, Universidade Federal da Paraíba

  Scheduling problems on which constraints are imposed with regard to the temporal distances between successive executions of the same task have numerous applications, ranging from task scheduling in real-time systems to automobile production on an assembly line. In this work, we introduce a new NP-hard optimization problem belonging to this class of scheduling problems, namely the Carousel Scheduling Problem (CSP). Our work presents a mathematical formulation based on mixed-integer linear programming (MILP) for the CSP and a series of cuts to improve its resolution via exact methods. Finally, we propose an iterative solution method which greatly reduces the number of variables in the CSP formulation. The reported computational experiments show that, for a given time horizon, the iterative method actually increases the number of instances solved up to optimality
  when compared to their direct solution via a MILP solver.

• 
  11:20 AM - 11:45 AM

  Global solution analysis of a simple pooling problem with application in the feed industry

  • Emilie Joannopoulos, presenter, Université de Sherbrooke
  • François Dubeau, Université de Sherbrooke
  • Jean-Pierre Dussault, Université de Sherbrooke
  • Mounir Haddou, Insa Rennes

  We present a specific pooling model which uses bi-linear objective and constraints. An absolute lower bound is available for this model. We conjecture that any local solution is a global minimizer for this simple instance and we will present several experiments to support it, motivated within a feed industry application.

• 
  11:45 AM - 12:10 PM

  Linear Fractional Approximations for Master Problems in Column Generation

  • Jacques Desrosiers, presenter, GERAD, HEC Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Hocine Bouarab, École Polytechnique de Montréal
  • Jean-Bertrand Gauthier, GERAD - HEC Montréal

  Successive approximations of the master problem are created to converge to optimality. For every approximation except the last one, the cost of the solution decreases whereas the sum of the variable values increases. Moreover, the minimum reduced cost also increases and converges to zero with a super-geometric growth rate.