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

Published online:
DOI: 10.5802/ojmo.25
Classification: 90C11
Keywords: Mixed-Integer Linear Programming, Cutting Plane Selection, Instance-Dependent Learning
Mark Turner 1, 2; Thorsten Koch 1, 2; Felipe Serrano 3, 2; Michael Winkler 4, 2

1 Chair of Software and Algorithms for Discrete Optimization, Institute of Mathematics, Technische Universität Berlin, Straße des 17. Juni 135, 10623 Berlin, Germany
2 Zuse Institute Berlin, Department of Mathematical Optimization, Takustr. 7, 14195 Berlin
3 Cardinal Operations GmbH, Englerallee 19 14195 Berlin, Germany
4 Gurobi GmbH, Ulmenstr. 37-39, 60325 Frankfurt am Main, Germany
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
     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},
     publisher = {Universit\'e de Montpellier},
     volume = {4},
     year = {2023},
     doi = {10.5802/ojmo.25},
     language = {en},
     url = {}
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
VL  - 4
PB  - Université de Montpellier
UR  -
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
%V 4
%I Université de Montpellier
%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.

[1] Tobias Achterberg Constraint integer programming, Ph. D. Thesis, TU Berlin (2007)

[2] Tobias Achterberg; Robert E. Bixby; Zonghao Gu; Edward Rothberg; Dieter Weninger Presolve reductions in mixed integer programming, INFORMS J. Comput., Volume 32 (2020) no. 2, pp. 473-506 | DOI | MR | Zbl

[3] Tobias Achterberg; Roland Wunderling Mixed integer programming: Analyzing 12 years of progress, Facets of combinatorial optimization, Springer, 2013, pp. 449-481 | DOI | Zbl

[4] Giuseppe Andreello; Alberto Caprara; Matteo Fischetti Embedding {0, 1/2}-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] Jimmy L. Ba; Jamie Ryan Kiros; Geoffrey E. Hinton Layer normalization (2016) (

[6] Maria-Florina Balcan; Travis Dick; Tuomas Sandholm; Ellen Vitercik Learning to branch, International Conference on Machine Learning, PMLR (2018), pp. 344-353

[7] Maria-Florina Balcan; Siddharth Prasad; Tuomas Sandholm; Ellen Vitercik Sample complexity of tree search configuration: Cutting planes and beyond, Adv. Neural Inf. Process. Syst., Volume 34 (2021)

[8] Radu Baltean-Lugojan; Pierre Bonami; Ruth Misener; Andrea Tramontani Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks (2019) (

[9] Ksenia Bestuzheva; Mathieu Besançon; Wei-Kun Chen; Antonia Chmiela; Tim Donkiewicz; Jasper van Doornmalen; Leon Eifler; Oliver Gaul; Gerald Gamrath; Ambros Gleixner; Leona Gottwald; Christoph Graczyk; Katrin Halbig; Alexander Hoen; Christopher Hojny; Rolf van der Hulst; Thorsten Koch; Marco Lübbecke; Stephen Maher; Frederic Matter; Erik Mühmer; Benjamin Müller; Marc E. Pfetsch; Daniel Rehfeldt; Steffan Schlein; Franziska Schlösser; Felipe Serrano; Yuji Shinano; Boro Sofranac; Mark Turner; Stefan Vigerske; Fabian Wegscheider; Philipp Wellner; Dieter Weninger; Jakob Witzig Enabling research through the SCIP optimization suite 8.0, ACM Trans. Math. Softw., Volume 49 (2023) no. 2, pp. 1-21 | DOI

[10] Quentin Cappart; Didier Chételat; Elias Khalil; Andrea Lodi; Christopher Morris; Petar Veličković Combinatorial optimization and reasoning with graph neural networks (2021) (

[11] Santanu S. Dey; Marco Molinaro Theoretical challenges towards cutting-plane selection, Math. Program., Volume 170 (2018) no. 1, pp. 237-266 | MR | Zbl

[12] Jian-Ya Ding; Chao Zhang; Lei Shen; Shengyin Li; Bing Wang; Yinghui Xu; Le Song 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] Matthias Fey; Jan E. Lenssen Fast Graph Representation Learning with PyTorch Geometric, ICLR Workshop on Representation Learning on Graphs and Manifolds (2019)

[14] Gerald Gamrath; Daniel Anderson; Ksenia Bestuzheva; Wei-Kun Chen; Leon Eifler; Maxime Gasse; Patrick Gemander; Ambros Gleixner; Leona Gottwald; Katrin Halbig; Gregor Hendel; Christopher Hojny; Thorsten Koch; Pierre Le Bodic; Stephen Maher; Frederic Matter; Matthias Miltenberger; Erik Mühmer; Benjamin Müller; Marc E. Pfetsch; Franziska Schlösser; Felipe Serrano; Yuji Shinano; Christine Tawfik; Stefan Vigerske; Fabian Wegscheider; Dieter Weninger; Jakob Witzig The SCIP Optimization Suite 7.0 (2020) no. 20-10 (ZIB-Report)

[15] Maxime Gasse; Didier Chételat; Nicola Ferroni; Laurent Charlin; Andrea Lodi Exact combinatorial optimization with graph convolutional neural networks (2019) (

[16] Ambros Gleixner; Gregor Hendel; Gerald Gamrath; Tobias Achterberg; Michael Bastubbe; Timo Berthold; Philipp Christophel; Kati Jarck; Thorsten Koch; Jeff Linderoth 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] Ian Goodfellow; Yoshua Bengio; Aaron Courville Deep learning, MIT Press, 2016

[18] Gurobi Optimization, LLC Gurobi Optimizer Reference Manual, 2021 (

[19] Zeren Huang; Kerong Wang; Furui Liu; Hui-ling Zhen; Weinan Zhang; Mingxuan Yuan; Jianye Hao; Yong Yu; Jun Wang Learning to Select Cuts for Efficient Mixed-Integer Programming (2021) (

[20] Diederik P. Kingma; Jimmy L. Ba Adam: A method for stochastic optimization (2014) (

[21] Marius Lindauer; Katharina Eggensperger; Matthias Feurer; André Biedenkapp; Difan Deng; Carolin Benjamins; Tim Ruhkopf; René Sass; Frank Hutter SMAC3: A Versatile Bayesian Optimization Package for Hyperparameter Optimization, J. Mach. Learn. Res., Volume 23 (2022) no. 54, pp. 1-9 | Zbl

[22] Stephen Maher; Matthias Miltenberger; Joao Pedro Pedroso; Daniel Rehfeldt; Robert Schwarz; Felipe Serrano PySCIPOpt: Mathematical programming in python with the SCIP optimization suite, International Congress on Mathematical Software, Springer (2016), pp. 301-307 | Zbl

[23] Hugues Marchand; Alexander Martin; Robert Weismantel; Laurence Wolsey Cutting planes in integer and mixed integer programming, Discrete Appl. Math., Volume 123 (2002) no. 1-3, pp. 397-446 | DOI | MR | Zbl

[24] Vinod Nair; Sergey Bartunov; Felix Gimeno; Ingrid von Glehn; Pawel Lichocki; Ivan Lobov; Brendan O’Donoghue; Nicolas Sonnerat; Christian Tjandraatmadja; Pengming Wang et al. Solving mixed integer programs using neural networks (2020) (

[25] Adam Paszke; Sam Gross; Francisco Massa; Adam Lerer; James Bradbury; Gregory Chanan; Trevor Killeen; Zeming Lin; Natalia Gimelshein; Luca Antiga; Alban Desmaison; Andreas Kopf; Edward Yang; Zachary DeVito; Martin Raison; Alykhan Tejani; Sasank Chilamkurthy; Benoit Steiner; Lu Fang; Junjie Bai; Soumith Chintala 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

[26] Benjamin Sanchez-Lengeling; Emily Reif; Adam Pearce; Alexander B. Wiltschko A gentle introduction to graph neural networks, Distill, Volume 6 (2021) no. 9, e33 | DOI

[27] Zachary Steever; Chase Murray; Junsong Yuan; Mark Karwan; Marco Lübbecke 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] Richard S. Sutton; Andrew G. Barto Reinforcement learning: An introduction, MIT Press, 2018

[29] Yunhao Tang; Shipra Agrawal; Yuri Faenza Reinforcement learning for integer programming: Learning to cut, International Conference on Machine Learning, PMLR (2020), pp. 9367-9376

[30] Franz Wesselmann; Uwe Stuhl Implementing cutting plane management and selection techniques (2012) (Technical report)

[31] Wolfram Research, Inc. Mathematica, Version 12.2, 2020 (

Cited by Sources: