Abstract | ||
---|---|---|
Computing the 1-width of the incidence matrix of a Steiner Triple System gives rise to highly symmetric and computationally challenging set covering problems. The largest instance solved so far corresponds to a Steiner Tripe System of order 81. We present optimal solutions for systems of orders 135 and 243. These are computed by a tailored implementation of constraint orbital branching, a method designed to exploit symmetry in integer programs. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.orl.2011.02.001 | Oper. Res. Lett. |
Keywords | Field | DocType |
steiner triple systems,constraint orbital,steiner tripe system,tailored implementation,largest instance,integer programming,steiner triple system,large steiner triple covering,incidence matrix,optimal solution,integer program,branch-and-bound algorithms,symmetry,set covering problem,branch and bound algorithm | Integer,Discrete mathematics,Combinatorics,Monad (category theory),Steiner tree problem,Integer programming,Incidence matrix,Mathematics,Branching (version control),Covering problems,Steiner system | Journal |
Volume | Issue | ISSN |
39 | 2 | Operations Research Letters |
Citations | PageRank | References |
6 | 0.53 | 9 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
James Ostrowski | 1 | 50 | 3.76 |
Jeff Linderoth | 2 | 654 | 50.26 |
Fabrizio Rossi | 3 | 140 | 16.33 |
Stefano Smriglio | 4 | 153 | 14.81 |