Jeffrey T. Linderoth, Associate Professor, University of Wisconsin-Madison

We will discuss our ongoing work aimed at solving integer programs that contain a great deal of symmetry. The first technique we present, orbital branching, is a method that is based on computing groups of variables that are equivalent with respect to the symmetry in the problem. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region which significantly reduces the effects of symmetry while still allowing a flexible branching rule. We also show how to exploit the symmetries present in the problem to fix variables throughout the branch-and-bound tree. Orbital branching can easily be incorporated into standard IP software. Through an empirical study on a test suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as isomorphism pruning.

We next will discuss how the orbital branching methodology can be extended so that the branching disjunction can be based on an arbitrary constraint. We will demonstrate how to use “constraint orbital branching”, in combination with enumerative procedures, to solve a decades-old problem on computing the incidence-width of a Steiner Triple System.

This is joint work with Jim Ostrowski (University of Waterloo) and Fabrizio Rossi and Stefano Smriglio (Universita di L’Aquila).