MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library

We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of 5,721 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, these sets were compiled using … Read more

The SCIP Optimization Suite 6.0

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion … Read more

A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations

In Dantzig-Wolfe reformulation of an integer program one convexifies a subset of the constraints, leading to potentially stronger dual bounds from the respective linear programming relaxation. As the subset can be chosen arbitrarily, this includes the trivial cases of convexifying no and all constraints, resulting in a weakest and strongest reformulation, respectively. Our computational study … Read more

A Branch-and-Price Algorithm for Capacitated Hypergraph Vertex Separation

We exactly solve the NP-hard combinatorial optimization problem of finding a minimum cardinality vertex separator with k (or arbitrarily many) capacitated shores in a hypergraph. We present an exponential size integer programming formulation which we solve by branch-and-price. The pricing problem, an interesting optimization problem on its own, has a decomposable structure that we exploit … Read more