We report on the selection process leading to the sixth version of the Mixed Integer Programming Library, MIPLIB 2017. Selected from an initial pool of 5721 instances, the new MIPLIB 2017 collection consists of 1065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, these sets were compiled using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encode requirements on diversity and balancedness with respect to instance features and performance data.
Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver adaptively concentrates its limited computational budget by learning which LNS heuristics work best for the MIP problem at hand. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts as a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search spaces, which we call auxiliary problems. The decision which auxiliary problem should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available auxiliary problems based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing prioritization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some LNS problems which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP.
Learning to use local cuts
(2025)
An essential component in modern solvers for mixed-integer (linear) programs (MIPs)
is the separation of additional inequalities (cutting planes) to tighten the linear pro-
gramming relaxation. Various algorithmic decisions are necessary when integrating
cutting plane methods into a branch-and-bound (B&B) solver as there is always the
trade-off between the efficiency of the cuts and their overhead, given that they tend
to slow down the solution time of the relaxation. One of the most crucial questions
is: Should cuts only be generated globally at the root or also locally at nodes of the
tree? We address this question by a machine learning approach for which we train a
regression forest to predict the speed-up (or slow-down) provided by using local cuts.
We demonstrate with an open implementation that this helps to improve the perfor-
mance of the FICO Xpress MIP solver on a public test set of general MIP instances.
We further report on the impact of a practical implementation inside Xpress on a large,
diverse set of real-world industry MIPs.