{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T12:51:41Z","timestamp":1774702301367,"version":"3.50.1"},"reference-count":31,"publisher":"MathDoc\/Centre Mersenne","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>\n                    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\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/github.com\/Opt-Mucca\/Adaptive-Cutsel-MILP\">https:\/\/github.com\/Opt-Mucca\/Adaptive-Cutsel-MILP<\/jats:ext-link>\n                    .\n                  <\/jats:p>","DOI":"10.5802\/ojmo.25","type":"journal-article","created":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T12:35:59Z","timestamp":1689856559000},"page":"1-28","source":"Crossref","is-referenced-by-count":12,"title":["Adaptive Cut Selection in Mixed-Integer Linear Programming"],"prefix":"10.5802","volume":"4","author":[{"given":"Mark","family":"Turner","sequence":"first","affiliation":[]},{"given":"Thorsten","family":"Koch","sequence":"additional","affiliation":[]},{"given":"Felipe","family":"Serrano","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Winkler","sequence":"additional","affiliation":[]}],"member":"3842","published-online":{"date-parts":[[2023,7,20]]},"reference":[{"key":"key2025101710011153621_1","author":"Achterberg, Tobias","year":"2007","unstructured":"[1] Achterberg, Tobias Constraint integer programming, Ph. D. Thesis, TU Berlin (2007)","journal-title":"Constraint integer programming"},{"issue":"2","key":"key2025101710011153621_2","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1287\/ijoc.2018.0857","article-title":"Presolve reductions in mixed integer programming","volume":"32","author":"Achterberg, Tobias","year":"2020","unstructured":"[2] Achterberg, Tobias; Bixby, Robert E.; Gu, Zonghao; Rothberg, Edward; Weninger, Dieter Presolve reductions in mixed integer programming, INFORMS J. Comput., Volume 32 (2020) no. 2, pp. 473-506","journal-title":"INFORMS J. Comput."},{"key":"key2025101710011153621_3","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-642-38189-8_18","article-title":"Mixed integer programming: Analyzing 12 years of progress","author":"Achterberg, Tobias","year":"2013","unstructured":"[3] Achterberg, Tobias; Wunderling, Roland Mixed integer programming: Analyzing 12 years of progress, Facets of combinatorial optimization, Springer, 2013, pp. 449-481","journal-title":"Facets of combinatorial optimization"},{"issue":"2","key":"key2025101710011153621_4","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1287\/ijoc.1050.0162","article-title":"Embedding <span class=\"mathjax-formula\" data-tex=\"$\\lbrace $\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mo>{<\/mo><\/math><\/span>0, <span class=\"mathjax-formula\" data-tex=\"$1\/2\\rbrace $\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mrow><mn>1<\/mn><mo>\/<\/mo><mn>2<\/mn><mo>}<\/mo><\/mrow><\/math><\/span>-Cuts in a Branch-and-Cut Framework: A Computational Study","volume":"19","author":"Andreello, Giuseppe","year":"2007","unstructured":"[4] Andreello, Giuseppe; Caprara, Alberto; Fischetti, Matteo 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","journal-title":"INFORMS J. Comput."},{"key":"key2025101710011153621_5","author":"Ba, Jimmy L.","year":"2016","unstructured":"[5] Ba, Jimmy L.; Kiros, Jamie Ryan; Hinton, Geoffrey E. Layer normalization (2016) (https:\/\/arxiv.org\/abs\/1607.06450)","journal-title":"Layer normalization"},{"key":"key2025101710011153621_6","first-page":"344","article-title":"Learning to branch","author":"Balcan, Maria-Florina","year":"2018","unstructured":"[6] Balcan, Maria-Florina; Dick, Travis; Sandholm, Tuomas; Vitercik, Ellen, International Conference on Machine Learning, PMLR (2018), pp. 344-353","journal-title":"International Conference on Machine Learning"},{"key":"key2025101710011153621_7","article-title":"Sample complexity of tree search configuration: Cutting planes and beyond","volume":"34","author":"Balcan, Maria-Florina","year":"2021","unstructured":"[7] Balcan, Maria-Florina; Prasad, Siddharth; Sandholm, Tuomas; Vitercik, Ellen Sample complexity of tree search configuration: Cutting planes and beyond, Adv. Neural Inf. Process. Syst., Volume 34 (2021)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"key2025101710011153621_8","author":"Baltean-Lugojan, Radu","year":"2019","unstructured":"[8] Baltean-Lugojan, Radu; Bonami, Pierre; Misener, Ruth; Tramontani, Andrea Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks (2019) (https:\/\/optimization-online.org\/2018\/11\/6943\/)","journal-title":"Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks"},{"issue":"2","key":"key2025101710011153621_9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3585516","article-title":"Enabling research through the SCIP optimization suite 8.0","volume":"49","author":"Bestuzheva, Ksenia","year":"2023","unstructured":"[9] Bestuzheva, Ksenia; Besan\u00e7on, Mathieu; Chen, Wei-Kun; Chmiela, Antonia; Donkiewicz, Tim; van Doornmalen, Jasper; Eifler, Leon; Gaul, Oliver; Gamrath, Gerald; Gleixner, Ambros; Gottwald, Leona; Graczyk, Christoph; Halbig, Katrin; Hoen, Alexander; Hojny, Christopher; Hulst, Rolf van der; Koch, Thorsten; L\u00fcbbecke, Marco; Maher, Stephen; Matter, Frederic; M\u00fchmer, Erik; M\u00fcller, Benjamin; Pfetsch, Marc E.; Rehfeldt, Daniel; Schlein, Steffan; Schl\u00f6sser, Franziska; Serrano, Felipe; Shinano, Yuji; Sofranac, Boro; Turner, Mark; Vigerske, Stefan; Wegscheider, Fabian; Wellner, Philipp; Weninger, Dieter; Witzig, Jakob Enabling research through the SCIP optimization suite 8.0, ACM Trans. Math. Softw., Volume 49 (2023) no. 2, pp. 1-21","journal-title":"ACM Trans. Math. Softw."},{"key":"key2025101710011153621_10","author":"Cappart, Quentin","year":"2021","unstructured":"[10] Cappart, Quentin; Ch\u00e9telat, Didier; Khalil, Elias; Lodi, Andrea; Morris, Christopher; Veli\u010dkovi\u0107, Petar Combinatorial optimization and reasoning with graph neural networks (2021) (https:\/\/arxiv.org\/abs\/2102.09544)","journal-title":"Combinatorial optimization and reasoning with graph neural networks"},{"issue":"1","key":"key2025101710011153621_11","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s10107-018-1302-4","article-title":"Theoretical challenges towards cutting-plane selection","volume":"170","author":"Dey, Santanu S.","year":"2018","unstructured":"[11] Dey, Santanu S.; Molinaro, Marco Theoretical challenges towards cutting-plane selection, Math. Program., Volume 170 (2018) no. 1, pp. 237-266","journal-title":"Math. Program."},{"key":"key2025101710011153621_12","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1609\/aaai.v34i02.5503","article-title":"Accelerating primal solution findings for mixed integer programs based on solution prediction","volume":"34","author":"Ding, Jian-Ya","year":"2020","unstructured":"[12] Ding, Jian-Ya; Zhang, Chao; Shen, Lei; Li, Shengyin; Wang, Bing; Xu, Yinghui; Song, Le 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","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"key2025101710011153621_13","article-title":"Fast Graph Representation Learning with PyTorch Geometric","author":"Fey, Matthias","year":"2019","unstructured":"[13] Fey, Matthias; Lenssen, Jan E., ICLR Workshop on Representation Learning on Graphs and Manifolds (2019)","journal-title":"ICLR Workshop on Representation Learning on Graphs and Manifolds"},{"issue":"20-10","key":"key2025101710011153621_14","author":"Gamrath, Gerald","year":"2020","unstructured":"[14] Gamrath, Gerald; Anderson, Daniel; Bestuzheva, Ksenia; Chen, Wei-Kun; Eifler, Leon; Gasse, Maxime; Gemander, Patrick; Gleixner, Ambros; Gottwald, Leona; Halbig, Katrin; Hendel, Gregor; Hojny, Christopher; Koch, Thorsten; Le Bodic, Pierre; Maher, Stephen; Matter, Frederic; Miltenberger, Matthias; M\u00fchmer, Erik; M\u00fcller, Benjamin; Pfetsch, Marc E.; Schl\u00f6sser, Franziska; Serrano, Felipe; Shinano, Yuji; Tawfik, Christine; Vigerske, Stefan; Wegscheider, Fabian; Weninger, Dieter; Witzig, Jakob The SCIP Optimization Suite 7.0 (2020) no. 20-10 http:\/\/nbn-resolving.de\/urn:nbn:de:0297-zib-78023 (ZIB-Report)","journal-title":"The SCIP Optimization Suite 7.0"},{"key":"key2025101710011153621_15","author":"Gasse, Maxime","year":"2019","unstructured":"[15] Gasse, Maxime; Ch\u00e9telat, Didier; Ferroni, Nicola; Charlin, Laurent; Lodi, Andrea Exact combinatorial optimization with graph convolutional neural networks (2019) (https:\/\/arxiv.org\/abs\/1906.01629)","journal-title":"Exact combinatorial optimization with graph convolutional neural networks"},{"issue":"3","key":"key2025101710011153621_16","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s12532-020-00194-3","article-title":"MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library","volume":"13","author":"Gleixner, Ambros","year":"2021","unstructured":"[16] Gleixner, Ambros; Hendel, Gregor; Gamrath, Gerald; Achterberg, Tobias; Bastubbe, Michael; Berthold, Timo; Christophel, Philipp; Jarck, Kati; Koch, Thorsten; Linderoth, Jeff 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","journal-title":"Math. Program. Comput."},{"key":"key2025101710011153621_17","author":"Goodfellow, Ian","year":"2016","unstructured":"[17] Goodfellow, Ian; Bengio, Yoshua; Courville, Aaron Deep learning, MIT Press, 2016","journal-title":"Deep learning"},{"key":"key2025101710011153621_18","article-title":"Gurobi Optimizer Reference Manual","author":"Gurobi Optimization, LLC","year":"2021","unstructured":"[18] Gurobi Optimization, LLC Gurobi Optimizer Reference Manual, 2021 (https:\/\/www.gurobi.com)"},{"key":"key2025101710011153621_19","author":"Huang, Zeren","year":"2021","unstructured":"[19] Huang, Zeren; Wang, Kerong; Liu, Furui; Zhen, Hui-ling; Zhang, Weinan; Yuan, Mingxuan; Hao, Jianye; Yu, Yong; Wang, Jun Learning to Select Cuts for Efficient Mixed-Integer Programming (2021) (https:\/\/arxiv.org\/abs\/2105.13645)","journal-title":"Learning to Select Cuts for Efficient Mixed-Integer Programming"},{"key":"key2025101710011153621_20","author":"Kingma, Diederik P.","year":"2014","unstructured":"[20] Kingma, Diederik P.; Ba, Jimmy L. Adam: A method for stochastic optimization (2014) (https:\/\/arxiv.org\/abs\/1412.6980)","journal-title":"Adam: A method for stochastic optimization"},{"issue":"54","key":"key2025101710011153621_21","first-page":"1","article-title":"SMAC3: A Versatile Bayesian Optimization Package for Hyperparameter Optimization","volume":"23","author":"Lindauer, Marius","year":"2022","unstructured":"[21] Lindauer, Marius; Eggensperger, Katharina; Feurer, Matthias; Biedenkapp, Andr\u00e9; Deng, Difan; Benjamins, Carolin; Ruhkopf, Tim; Sass, Ren\u00e9; Hutter, Frank 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","journal-title":"J. Mach. Learn. Res."},{"key":"key2025101710011153621_22","first-page":"301","article-title":"PySCIPOpt: Mathematical programming in python with the SCIP optimization suite","author":"Maher, Stephen","year":"2016","unstructured":"[22] Maher, Stephen; Miltenberger, Matthias; Pedroso, Joao Pedro; Rehfeldt, Daniel; Schwarz, Robert; Serrano, Felipe PySCIPOpt: Mathematical programming in python with the SCIP optimization suite, International Congress on Mathematical Software, Springer (2016), pp. 301-307","journal-title":"International Congress on Mathematical Software"},{"issue":"1-3","key":"key2025101710011153621_23","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/S0166-218X(01)00348-1","article-title":"Cutting planes in integer and mixed integer programming","volume":"123","author":"Marchand, Hugues","year":"2002","unstructured":"[23] Marchand, Hugues; Martin, Alexander; Weismantel, Robert; Wolsey, Laurence Cutting planes in integer and mixed integer programming, Discrete Appl. Math., Volume 123 (2002) no. 1-3, pp. 397-446","journal-title":"Discrete Appl. Math."},{"key":"key2025101710011153621_24","author":"Nair, Vinod","year":"2020","unstructured":"[24] Nair, Vinod; Bartunov, Sergey; Gimeno, Felix; von Glehn, Ingrid; Lichocki, Pawel; Lobov, Ivan; O\u2019Donoghue, Brendan; Sonnerat, Nicolas; Tjandraatmadja, Christian; Wang, Pengming et al. Solving mixed integer programs using neural networks (2020) (https:\/\/arxiv.org\/abs\/2012.13349)","journal-title":"Solving mixed integer programs using neural networks"},{"key":"key2025101710011153621_25","first-page":"8024","article-title":"PyTorch: An Imperative Style, High-Performance Deep Learning Library","author":"Paszke, Adam","year":"2019","unstructured":"[25] Paszke, Adam; Gross, Sam; Massa, Francisco; Lerer, Adam; Bradbury, James; Chanan, Gregory; Killeen, Trevor; Lin, Zeming; Gimelshein, Natalia; Antiga, Luca; Desmaison, Alban; Kopf, Andreas; Yang, Edward; DeVito, Zachary; Raison, Martin; Tejani, Alykhan; Chilamkurthy, Sasank; Steiner, Benoit; Fang, Lu; Bai, Junjie; Chintala, Soumith PyTorch: An Imperative Style, High-Performance Deep Learning Library, Advances in Neural Information Processing Systems 32 (Wallach, H.; Larochelle, H.; Beygelzimer, A.; d\u2019Alch\u00e9-Buc, F.; Fox, E.; Garnett, R., eds.), 2019, pp. 8024-8035 http:\/\/papers.neurips.cc\/paper\/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf","journal-title":"Advances in Neural Information Processing Systems 32"},{"issue":"9","key":"key2025101710011153621_26","doi-asserted-by":"publisher","DOI":"10.23915\/distill.00033","article-title":"A gentle introduction to graph neural networks","volume":"6","author":"Sanchez-Lengeling, Benjamin","year":"2021","unstructured":"[26] Sanchez-Lengeling, Benjamin; Reif, Emily; Pearce, Adam; Wiltschko, Alexander B. A gentle introduction to graph neural networks, Distill, Volume 6 (2021) no. 9, e33","journal-title":"Distill"},{"issue":"4","key":"key2025101710011153621_27","doi-asserted-by":"publisher","first-page":"1849","DOI":"10.1287\/ijoc.2021.1117","article-title":"An Image-based Approach to Detecting Structural Similarity Among Mixed Integer Programs","volume":"34","author":"Steever, Zachary","year":"2022","unstructured":"[27] Steever, Zachary; Murray, Chase; Yuan, Junsong; Karwan, Mark; L\u00fcbbecke, Marco An Image-based Approach to Detecting Structural Similarity Among Mixed Integer Programs, INFORMS J. Comput., Volume 34 (2022) no. 4, pp. 1849-1870","journal-title":"INFORMS J. Comput."},{"key":"key2025101710011153621_28","author":"Sutton, Richard S.","year":"2018","unstructured":"[28] Sutton, Richard S.; Barto, Andrew G. Reinforcement learning: An introduction, MIT Press, 2018","journal-title":"Reinforcement learning: An introduction"},{"key":"key2025101710011153621_29","first-page":"9367","article-title":"Reinforcement learning for integer programming: Learning to cut","author":"Tang, Yunhao","year":"2020","unstructured":"[29] Tang, Yunhao; Agrawal, Shipra; Faenza, Yuri, International Conference on Machine Learning, PMLR (2020), pp. 9367-9376","journal-title":"International Conference on Machine Learning"},{"key":"key2025101710011153621_30","author":"Wesselmann, Franz","year":"2012","unstructured":"[30] Wesselmann, Franz; Stuhl, Uwe Implementing cutting plane management and selection techniques (2012) (Technical report)","journal-title":"Implementing cutting plane management and selection techniques"},{"key":"key2025101710011153621_31","article-title":"Mathematica, Version 12.2","author":"Wolfram Research, Inc.","year":"2020","unstructured":"[31] Wolfram Research, Inc. Mathematica, Version 12.2, 2020 (https:\/\/www.wolfram.com\/mathematica)"}],"container-title":["Open Journal of Mathematical Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/ojmo.centre-mersenne.org\/item\/10.5802\/ojmo.25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T08:02:51Z","timestamp":1760688171000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojmo.centre-mersenne.org\/articles\/10.5802\/ojmo.25\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,20]]},"references-count":31,"alternative-id":["10.5802\/ojmo.25"],"URL":"https:\/\/doi.org\/10.5802\/ojmo.25","relation":{},"ISSN":["2777-5860"],"issn-type":[{"value":"2777-5860","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,20]]},"article-number":"5"}}