Optimization Days 2017
HEC Montréal, May 8-10, 2017
1st Canadian Healthcare Optimization Workshop (CHOW)
HEC Montréal, May 10-11, 2017
HEC Montréal, 8 — 11 May 2017
WB4 Optimisation combinatoire 2 / Combinatorial optimization 2
May 10, 2017 10:30 AM – 12:10 PM
Location: Meloche Monnex
Chaired by Jacques Desrosiers
10:30 AM - 10:55 AM
A k-medians model for semi-supervised 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 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
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
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
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.