Optimization Online


How important are branching decisions: fooling MIP solvers

Pierre Le Bodic (lebodic***at***gatech.edu)
George L. Nemhauser (george.nemhauser***at***isye.gatech.edu)

Abstract: We show the importance of selecting good branching variables by exhibiting a family of instances for which an optimal solution is both trivial to find and provably optimal by a fixed-size branch-and-bound tree, but for which state-of-the-art Mixed Integer Programming solvers need an increasing amount of resources. The instances encode the edge-coloring problem on a family of graphs containing a small subgraph requiring four colors, while the rest of the graph requires only three.

Keywords: mixed integer programming solvers, branch and bound, tree size, edge coloring, chromatic index

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


Download: [PDF]

Entry Submitted: 04/21/2014
Entry Accepted: 04/21/2014
Entry Last Modified: 05/01/2014

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 Optimization Society