Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142086 | Operations Research Letters | 2015 | 6 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Pierre Le Bodic, George L. Nemhauser,