Adaptive cut selection in mixed-integer linear programming
From MaRDI portal
Abstract: Cutting plane selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter tuning. Cut selection scoring rules are usually weighted sums of different measurements, where the weights are parameters. We present a parametric family of mixed-integer linear programs together with infinitely many family-wide valid cuts. Some of these cuts can induce integer optimal solutions directly after being applied, while others fail to do so even if an infinite amount are applied. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values, which select integer optimal inducing cuts in an infinite amount of our problems. We propose a variation on the design of existing graph convolutional neural networks, adapting them to learn cut selection rule parameters. We present a reinforcement learning framework for selecting cuts, and train our design using said framework over MIPLIB 2017 and a neural network verification data set. Our framework and design show that adaptive cut selection does substantially improve performance over a diverse set of instances, but that finding a single function describing such a rule is difficult. Code for reproducing all experiments is available at https://github.com/Opt-Mucca/Adaptive-Cutsel-MILP.
Recommendations
Cites work
- \textsc{PySCIPOpt}: mathematical programming in Python with the SCIP optimization suite
- An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs
- Cutting planes in integer and mixed integer programming
- Deep learning
- Embedding \(\{0, \frac{1}{2}\}\)-cuts in a branch-and-cut framework: a computational study
- scientific article; zbMATH DE number 7124428 (Why is no real title available?)
- MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library
- Mixed integer programming: analyzing 12 years of progress
- Presolve Reductions in Mixed Integer Programming
- Reinforcement learning. An introduction
- SMAC3: a versatile Bayesian optimization package for hyperparameter optimization
- Theoretical challenges towards cutting-plane selection
Cited in
(6)- Continuous cutting plane algorithms in integer programming
- Cutting plane selection with analytic centers and multiregression
- Online learning for scheduling MIP heuristics
- Learning to optimize: a tutorial for continuous and mixed-integer optimization
- Enhancing cut selection through reinforcement learning
- Machine learning augmented branch and bound for mixed integer linear programming
This page was built for publication: Adaptive cut selection in mixed-integer linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168887)
