-

 

 

 




Optimization Online





 

Improved strategies for branching on general disjunctions

Gerard Cornuejols (gc0v***at***andrew.cmu.edu)
Leo Liberti (liberti***at***lix.polytechnique.fr)
Giacomo Nannicini (giacomon***at***lix.polytechnique.fr)

Abstract: Within the context of solving Mixed-Integer Linear Programs by a Branch-and-Cut algorithm, we propose a new strategy for branching. Computational experiments show that, on the majority of our test instances, this approach enumerates fewer nodes than traditional branching. On average, on instances that contain both integer and continuous variables the number of nodes in the enumeration tree is reduced by more than a factor of two, and computing time is comparable. On a few instances, the improvements are of several orders of magnitude in both number of nodes and computing time.

Keywords: integer programming, branch and bound, split disjunctions

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: http://www.springerlink.com/content/mr7368x254t49822/

Download:

Entry Submitted: 08/21/2008
Entry Accepted: 08/21/2008
Entry Last Modified: 10/28/2010

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society