Title: Symmetry in Integer Programming
Speaker: James Ostrowski, Assistant Professor, Tennessee
Abstract: This talk will focus on solving integer programs whose feasible regions are highly symmetric. Symmetry has long been recognized as a curse for solving integer programs, and auxiliary (often extended) formulations are sought to reduce the amount of symmetry in an Integer Programming (IP) formulation. If not properly addressed, branch-and-bound trees for highly symmetric problems can contain many thousands of nodes representing equivalent subproblems. Solving each of these subproblems results in a tremendous waste of computational resources and can make what should be very simple problems impossible to solve.
This talk will explain why symmetry breaking methods are necessary for many important classes of problems, including graph coloring, cutting stock, statistical design problems, and scheduling problems. This talk will also discuss an effective branching method for dealing with highly symmetric problems, orbital branching. Orbital branching uses information provided by the symmetry group to create branching disjunctions that reduce the likelihood that equivalent nodes are evaluated. It is applicable for a wide array of problems and has recently been incorporated into Gurobi, a leading commercial IP solver.