Titre :
Symmetry in Mathematical Programming

Conférencier :
LIBERTI, Leo (LIX, École Polytechnique, France)

Résumé :
When solving Mathematical Programming (MP) problems using Branch-and-Bound (BB), be they linear or nonlinear, continuous or mixed-integer, the presence of symmetries of the solution set results in BB taking longer than strictly needed, due to the symmetries induced on the BB tree. I shall illustrate a class of 'symmetry breaking' methods based on reformulating the symmetric MPs so that some of the symmetric optima become infeasible. I shall show how to automatically detect MP formulation symmetries by reducing MP to graphs, and how to automatically generate reformulated MPs with (hopefully) fewer symmetric optima. Although computational tests show that reformulations may not always succeed in making BB terminate faster, they can be applied very efficiently --- so they can be considered an efficient 'pre-solving step' to running BB.