Solving Large Steiner Triple Covering Problems

James Ostrowski(jostrowengmail.uwaterloo.ca)
Jeff Linderoth(linderothwisc.edu)
Fabrizio Rossi(fabrizio.rossiunivaq.it)
Stefano Smriglio(stefano.smrigliounivaq.it)

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.

Keywords: Integer programming, symmetry, branch-and-bound algorithms, Steiner Triple Systems

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation:

Download: [PDF]

Entry Submitted: 09/22/2009
Entry Accepted: 09/24/2009
Entry Last Modified: 09/22/2009

Modify/Update this entry