Adaptive Cut Selection in Mixed-Integer Linear Programming
Open Journal of Mathematical Optimization, Volume 4 (2023), article no. 5, 28 p.
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.
Received:
Revised:
Accepted:
Published online:
DOI:
10.5802/ojmo.25
Revised:
Accepted:
Published online:
Classification:
90C11
Keywords: Mixed-Integer Linear Programming, Cutting Plane Selection, Instance-Dependent Learning
Keywords: Mixed-Integer Linear Programming, Cutting Plane Selection, Instance-Dependent Learning
Author's affiliations:
Mark Turner 1, 2;
Thorsten Koch 1, 2;
Felipe Serrano 3, 2;
Michael Winkler 4, 2
License: 
CC-BY 4.0
CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{OJMO_2023__4__A5_0,
author = {Mark Turner and Thorsten Koch and Felipe Serrano and Michael Winkler},
title = {Adaptive {Cut} {Selection} in {Mixed-Integer} {Linear} {Programming}},
journal = {Open Journal of Mathematical Optimization},
eid = {5},
pages = {1--28},
publisher = {Universit\'e de Montpellier},
volume = {4},
year = {2023},
doi = {10.5802/ojmo.25},
language = {en},
url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.25/}
}
TY - JOUR AU - Mark Turner AU - Thorsten Koch AU - Felipe Serrano AU - Michael Winkler TI - Adaptive Cut Selection in Mixed-Integer Linear Programming JO - Open Journal of Mathematical Optimization PY - 2023 SP - 1 EP - 28 VL - 4 PB - Université de Montpellier UR - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.25/ DO - 10.5802/ojmo.25 LA - en ID - OJMO_2023__4__A5_0 ER -
%0 Journal Article %A Mark Turner %A Thorsten Koch %A Felipe Serrano %A Michael Winkler %T Adaptive Cut Selection in Mixed-Integer Linear Programming %J Open Journal of Mathematical Optimization %D 2023 %P 1-28 %V 4 %I Université de Montpellier %U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.25/ %R 10.5802/ojmo.25 %G en %F OJMO_2023__4__A5_0
Mark Turner; Thorsten Koch; Felipe Serrano; Michael Winkler. Adaptive Cut Selection in Mixed-Integer Linear Programming. Open Journal of Mathematical Optimization, Volume 4 (2023), article no. 5, 28 p. doi : 10.5802/ojmo.25. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.25/
[1] Constraint integer programming, Ph. D. Thesis, TU Berlin (2007)
[2] Presolve reductions in mixed integer programming, INFORMS J. Comput., Volume 32 (2020) no. 2, pp. 473-506 | DOI | MR | Zbl
[3] Mixed integer programming: Analyzing 12 years of progress, Facets of combinatorial optimization, Springer, 2013, pp. 449-481 | DOI | Zbl
[4] Embedding 0, -Cuts in a Branch-and-Cut Framework: A Computational Study, INFORMS J. Comput., Volume 19 (2007) no. 2, pp. 229-238 | DOI | MR | Zbl
[5] Layer normalization (2016) (https://arxiv.org/abs/1607.06450)
[6] Learning to branch, International Conference on Machine Learning, PMLR (2018), pp. 344-353
[7] Sample complexity of tree search configuration: Cutting planes and beyond, Adv. Neural Inf. Process. Syst., Volume 34 (2021)
[8] Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks (2019) (https://optimization-online.org/2018/11/6943/)
[9] Enabling research through the SCIP optimization suite 8.0, ACM Trans. Math. Softw., Volume 49 (2023) no. 2, pp. 1-21 | DOI
[10] Combinatorial optimization and reasoning with graph neural networks (2021) (https://arxiv.org/abs/2102.09544)
[11] Theoretical challenges towards cutting-plane selection, Math. Program., Volume 170 (2018) no. 1, pp. 237-266 | MR | Zbl
[12] Accelerating primal solution findings for mixed integer programs based on solution prediction, Proceedings of the AAAI Conference on Artificial Intelligence, Volume 34 (2020), pp. 1452-1459 | DOI
[13] Fast Graph Representation Learning with PyTorch Geometric, ICLR Workshop on Representation Learning on Graphs and Manifolds (2019)
[14] The SCIP Optimization Suite 7.0 (2020) no. 20-10 http://nbn-resolving.de/urn:nbn:de:0297-zib-78023 (ZIB-Report)
[15] Exact combinatorial optimization with graph convolutional neural networks (2019) (https://arxiv.org/abs/1906.01629)
[16] et al. MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library, Math. Program. Comput., Volume 13 (2021) no. 3, pp. 443-490 | DOI | MR | Zbl
[17] Deep learning, MIT Press, 2016
[18] Gurobi Optimizer Reference Manual, 2021 (https://www.gurobi.com)
[19] Learning to Select Cuts for Efficient Mixed-Integer Programming (2021) (https://arxiv.org/abs/2105.13645)
[20] Adam: A method for stochastic optimization (2014) (https://arxiv.org/abs/1412.6980)
[21] SMAC3: A Versatile Bayesian Optimization Package for Hyperparameter Optimization, J. Mach. Learn. Res., Volume 23 (2022) no. 54, pp. 1-9 http://jmlr.org/papers/v23/21-0888.html | Zbl
[22] PySCIPOpt: Mathematical programming in python with the SCIP optimization suite, International Congress on Mathematical Software, Springer (2016), pp. 301-307 | Zbl
[23] Cutting planes in integer and mixed integer programming, Discrete Appl. Math., Volume 123 (2002) no. 1-3, pp. 397-446 | DOI | MR | Zbl
[24] et al. Solving mixed integer programs using neural networks (2020) (https://arxiv.org/abs/2012.13349)
[25] PyTorch: An Imperative Style, High-Performance Deep Learning Library, Advances in Neural Information Processing Systems 32 (H. Wallach; H. Larochelle; A. Beygelzimer; F. d’Alché-Buc; E. Fox; R. Garnett, eds.), 2019, pp. 8024-8035 http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf
[26] A gentle introduction to graph neural networks, Distill, Volume 6 (2021) no. 9, e33 | DOI
[27] An Image-based Approach to Detecting Structural Similarity Among Mixed Integer Programs, INFORMS J. Comput., Volume 34 (2022) no. 4, pp. 1849-1870 | DOI | MR | Zbl
[28] Reinforcement learning: An introduction, MIT Press, 2018
[29] Reinforcement learning for integer programming: Learning to cut, International Conference on Machine Learning, PMLR (2020), pp. 9367-9376
[30] Implementing cutting plane management and selection techniques (2012) (Technical report)
[31] Mathematica, Version 12.2, 2020 (https://www.wolfram.com/mathematica)
Cited by Sources:
