Name
Abstract | ||
|---|---|---|
Orbital branching is a method for branching on variables in integer programming that reduces the likelihood of evaluating redundant, isomorphic nodes in the branch-and-bound procedure. In this work, the orbital branching methodology is extended so that the branching disjunction can be based on an arbitrary constraint. Many important families of integer programs are structured such that small instances from the family are embedded in larger instances. This structural information can be exploited to define a group of strong constraints on which to base the orbital branching disjunction. The symmetric nature of the problems is further exploited by enumerating non-isomorphic solutions to instances of the small family and using these solutions to create a collection of typically easy-to-solve integer programs. The solution of each integer program in the collection is equivalent to solving the original large instance. The effectiveness of this methodology is demonstrated by computing the optimal incidence width of Steiner Triple Systems and minimum cardinality covering designs. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-68891-4_16 | Integer Programming and Combinatorial Optimization |
Keywords | Field | DocType |
isomorphic node,branch-and-bound algorithms,steiner triple systems,constraint orbital,important family,small family,easy-to-solve integer program,covering designs,arbitrary constraint,integer programming,integer program,small instance,branch-and-bound procedure,symmetry,branch and bound,branch and bound algorithm,steiner triple system | Integer,Discrete mathematics,Mathematical optimization,Combinatorics,Computer science,Branch and cut,Branch and price,Cardinality,Isomorphism,Integer programming,Linear programming relaxation,Steiner system | Conference |
Volume | ISSN | ISBN |
5035 | 0302-9743 | 3-540-68886-2 |
Citations | PageRank | References |
11 | 0.86 | 11 |
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 |