Symmetry in Mathematical Programming: Orbital Shrinking

Leo Liberti

Event Location: 

453 Mohler Lab

Nature loves symmetry. Artists love symmetry. People love symmetry. Mathematicians and computer scientists also love symmetry, with the only exception of mathematical programmers, who always want to break it. Why? Symmetry is of great help in simplifying optimization in a convex setting, but in the discrete case it can trick search algorithms because symmetric solutions are visited time and again. The usual approach to deal with this issue is to destroy symmetry by introducing artificial constraints in the formulation, or by using a clever branching strategy during search. We will outline a different approach, called orbital shrinking, where additional integer variables expressing variable sums within each orbit are used to "encapsulate" model symmetry.

Bio Sketch: 

Leo Liberti graduated in Mathematics from Imperial College London and the University of Turin, Italy, and received his Ph.D.~in optimization from Imperial College. He was a postdoctoral fellow at Politecnico di Milano, then a professor at Ecole Polytechnique, France. He is now Research Staff Member at the IBM "TJ Watson" research center in Yorktown Heights. He puts his efforts in helping to shape two communities: Mixed-Integer Nonlinear Programming, and Distance Geometry.