Solving Large Steiner Triple Covering Problems

File(s):

Author(s): Ostrowski, Jim; Linderoth, Jeff; Rossi, Fabrizio; Smriglio, Stefano
Publisher: University of Wisconsin-Madison Department of Computer Sciences
Date: Mar 15, 2012
Abstract: Computing the 1-width of the incidence matrix of a Steiner Triple System gives rise to small set covering instances that provide a computational challenge for integer programming techniques. One major source of difficulty for instances of this family is their highly symmetric structure, which impairs the performance of most branch-and-bound algorithms. The largest instance in the family that has been solved corresponds to a Steiner Tripe System of order 81. We present optimal solutions to the set covering problems associated with systems of orders 135 and 243. The solutions are obtained by a tailored implementation of constraint orbital branching, a method for branching on general disjunctions designed to exploit symmetry in integer programs.
Permanent link: http://digital.library.wisc.edu/1793/60688
Export: Export to RefWorks