Groupe d’études et de recherche en analyse des décisions

Breaking Symmetry in Consecutive Edge-Coloring

Sivan Altinakar Polytechnique Montréal, Canada

The Consecutive Edge-Coloring Problem, a special case of edge-coloring in graph theory, aims to minimize the sum of the span of colors (or integers) incident to each vertex. This problem has applications in scheduling, for example when difficulties arise for storing a job in an intermediate state (due to chemical or spatial constraints), after it has been processed by some machines and while waiting for the next one to be available. It is also known to be NP-hard, and may be difficult to solve exactly, even for a very small number of vertices.

In this talk, we first compare different modeling approaches using Mixed Integer Programming and Constraint Programming. Then, we present a methodology to break some of the symmetry in this problem by using different subsets of Lexicographical Leader constraints, based either on a simple and fast analysis of the graph, or a set of generators of its automorphisms.

Join work with Gilles Caporossi and Alain Hertz.