Optimization Online


Solving Large Steiner Triple Covering Problems

James Ostrowski(jostrow***at***engmail.uwaterloo.ca)
Jeff Linderoth(linderoth***at***wisc.edu)
Fabrizio Rossi(fabrizio.rossi***at***univaq.it)
Stefano Smriglio(stefano.smriglio***at***univaq.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 )


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society