Symmetry in Integer Programming
| Speaker: | Jim Ostrowsky |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
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 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.