Optimization Online


Constraint Orbital Branching

James Ostrowski(jao204***at***lehigh.edu)
Jeff Linderoth(linderoth***at***wisc.edu)
Fabrizio Rossi(rossi***at***di.univaq.it)
Stefano Smriglio(smriglio***at***di.univaq.it)

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.

Keywords: Integer programming; symmetry; branch-and-bound

Category 1: Integer Programming

Category 2: Applications -- Science and Engineering (Statistics )


Download: [PDF]

Entry Submitted: 01/01/2008
Entry Accepted: 01/01/2008
Entry Last Modified: 01/01/2008

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