Friday, December 4, 2009
3:30 pm, MC 5158

Tutte Seminar Series
Combinatorics & Optimization
Fall 2009


Jim Ostrowsky
Dept. of Management Sciences, University of Waterloo

Symmetry in Integer Programming

Symmetry has long been considered a curse in integer linear programming, and auxiliary (often extended) formulations are sought to reduce the amount of symmetry in an integer linear programming (ILP) formulation. A standard method for solving integer programs is {\em branch-and-bound}. In branch-and-bound, the set of feasible solutions is partitioned, forming more easily-solved subproblems. The presence of symmetry means that many of these subproblems are equivalent. Only one member of each collection of equivalent subproblems needs to be solved. Failure to recognize that many subproblems are equivalent results in a waste of computational resources. In this talk, we will discuss how to recognize and exploit the symmetry of an ILP, as well as discuss why the current methods of dealing with symmetry are not enough.