Optimization Online


Orbital Branching

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

Abstract: We introduce orbital branching, an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry which is not present at the root node. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region which significantly reduces the effects of symmetry while still allowing a flexible branching rule. We also show how to exploit the symmetries present in the problem to fix variables throughout the branch-and-bound tree. Orbital branching can easily be incorporated into standard IP software. Through an empirical study on a test suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as isomorphism pruning and significantly better than a state-of-the-art commercial solver on symmetric integer programs.

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

Category 1: Integer Programming (0-1 Programming )

Citation: Technical Report 06T-007, Lehigh University Department of Industrial and Systems Engineering

Download: [PDF]

Entry Submitted: 11/15/2006
Entry Accepted: 11/16/2006
Entry Last Modified: 11/16/2006

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