Journées de l'optimisation 2014
Incluant une Journée industrielle de l'optimisation
HEC Montréal, 5  7 mai 2014
JOPT2014
HEC Montréal, 5 — 7 mai 2014
WB6 Optimisation combinatoire / Combinatorial Optimization
7 mai 2014 11h00 – 12h40
Salle: StHubert
Présidée par JeanYves Potvin
4 présentations

11h00  11h25
Solving the Clique Partitioning Problem as a Maximally Diverse Grouping Problem
We show that the Clique Partitioning Problem can be reformulated as the Maximally Diverse Grouping Problem(MDGP). We then modify a skewed general variable neighborhood search heuristic that was first developed to solve the MDGP. As
with the MDGP, the new heuristic achieves a significant improvement over the state of the art. 
11h25  11h50
A New Variant of the Assignment Problem: Application, NPHardness and Algorithms
The paper proposes a new variant of the classical assignment problem which arises in important applications such as health care and inventory management. A proof of its NPhardness is discussed. Furthermore, an emerging solution technique of Artificial Intelligence and Cohort Intelligence is applied to efficiently solve the problem. The results are compared to solutions obtained by CPLEX.

11h50  12h15
Finding Totally Independent Spanning Trees with Integer Programming
Two spanning trees of an undirected graph are totally independent if they are edge disjoint and if the unique paths that connect any pair of vertices in these trees are also node disjoint. Accordingly, K spanning trees are totally independent if they are pairwise totally independent. The problem of finding K totally independent spanning trees (KTIST) or proving that no such trees do exist is NPComplete. We investigate KTIST and two optimization problems derived from it. One of them consists in
finding the maximum K such that G has K totally independent trees. The other consists of finding K totally independent spanning trees with the minimum possible number of central nodes. We discuss integer programming formulations, valid inequalities and and exact solution approaches, Branchandcut and Branchandprice algorithms, to solve them. 
12h15  12h40
A MultiColoring Problem with Constrained Color Class Sizes
We consider an extension of the graph coloring problem with application in scheduling. Each vertex must be given multiple different colors, and bounds on the size of each color class must be respected. Two different tabu search approaches (relying on different search spaces) are proposed and compared.