Journées de l'optimisation 2017
HEC Montréal, 810 mai 2017
1^{er} Atelier Canadien sur l'optimisation des soins de santé (CHOW)
HEC Montréal, 1011 mai 2017
JOPT2017
HEC Montréal, 8 — 11 mai 2017
WB4 Optimisation combinatoire 2 / Combinatorial optimization 2
10 mai 2017 10h30 – 12h10
Salle: Meloche Monnex
Présidée par Jacques Desrosiers
4 présentations

10h30  10h55
A kmedians model for semisupervised clustering
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 semisupervised clustering. This work explores semisupervised clustering using the kmedians model. Results shows that (i) the model presents classification accuracy compared to that of the typical kmeans approach, and (ii) it allows to efficiently explore dual information in order to guide cluster analysis.

10h55  11h20
ANNULÉ / CANCELED: The Carousel Scheduling Problem
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 realtime systems to automobile production on an assembly line. In this work, we introduce a new NPhard optimization problem belonging to this class of scheduling problems, namely the Carousel Scheduling Problem (CSP). Our work presents a mathematical formulation based on mixedinteger 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. 
11h20  11h45
Global solution analysis of a simple pooling problem with application in the feed industry
We present a specific pooling model which uses bilinear 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.

11h45  12h10
Linear Fractional Approximations for Master Problems in Column Generation
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 supergeometric growth rate.