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

Symmetries in integer linear programs

Claire Lucas

Due to identical entities in practical problems or simplifications during the modeling phase, symmetries often arise in mathematical programs. This results in a decrease of computation efficiency, especially when the problem contains many integer variables. In this context the problem can be really difficult to solve with a usual branch-and-bound or branch-and-cut algorithm. Indeed, many identical subproblems will be solved in the enumeration tree, causing an important waste of computational effort. In this seminar, we will present the problem formally and introduce some classical static and dynamic strategies which reduce symmetry.