About This Item

Ask the MINDS@UW Librarian

Solving Large Steiner Triple Covering Problems

Show full item record


Ostrowski, Jim; Linderoth, Jeff; Rossi, Fabrizio; Smriglio, Stefano
University of Wisconsin-Madison Department of Computer Sciences
Mar 15, 2012
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
Export to RefWorks 

Part of

Show full item record

Search and browse


Deposit materials

  1. Register to deposit in MINDS@UW
  2. Need deposit privileges? Contact us.
  3. Already registered? Have deposit privileges? Deposit materials.