About This Item

Ask the MINDS@UW Librarian

Solving Large Steiner Triple Covering Problems

Show full item record

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 
‚Äč

Part of

Show full item record

Search and browse




About MINDS@UW

Deposit materials

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