Leo Liberti, the director of the Optimisation and Sustainable Development Chair at Ecole Polytechnique, will be giving a seminar on Monday 19th November, 2012, at 11am-12, in Jack Cole 1.33a.

Symmetry in Mathematical Programming

Abstract: When solving Mathematical Programming (MP) problems (be they linear or nonlinear, continuous or mixed-integer) using Branch-and-Bound (BB), 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.