Adaptive Cut Selection in Mixed-Integer Linear Programming
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 tunin...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2023-07-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.25/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825205037345800192 |
|---|---|
| author | Turner, Mark Koch, Thorsten Serrano, Felipe Winkler, Michael |
| author_facet | Turner, Mark Koch, Thorsten Serrano, Felipe Winkler, Michael |
| author_sort | Turner, Mark |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-dbe5d0cbe31e4a98b43070f01d04eadf |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2023-07-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-dbe5d0cbe31e4a98b43070f01d04eadf2025-02-07T14:02:56ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602023-07-01412810.5802/ojmo.2510.5802/ojmo.25Adaptive Cut Selection in Mixed-Integer Linear ProgrammingTurner, Mark0Koch, Thorsten1Serrano, Felipe2Winkler, Michael3Chair of Software and Algorithms for Discrete Optimization, Institute of Mathematics, Technische Universität Berlin, Straße des 17. Juni 135, 10623 Berlin, Germany; Zuse Institute Berlin, Department of Mathematical Optimization, Takustr. 7, 14195 BerlinChair of Software and Algorithms for Discrete Optimization, Institute of Mathematics, Technische Universität Berlin, Straße des 17. Juni 135, 10623 Berlin, Germany; Zuse Institute Berlin, Department of Mathematical Optimization, Takustr. 7, 14195 BerlinCardinal Operations GmbH, Englerallee 19 14195 Berlin, Germany; Zuse Institute Berlin, Department of Mathematical Optimization, Takustr. 7, 14195 BerlinGurobi GmbH, Ulmenstr. 37-39, 60325 Frankfurt am Main, Germany; Zuse Institute Berlin, Department of Mathematical Optimization, Takustr. 7, 14195 BerlinCutting 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.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.25/Mixed-Integer Linear ProgrammingCutting Plane SelectionInstance-Dependent Learning |
| spellingShingle | Turner, Mark Koch, Thorsten Serrano, Felipe Winkler, Michael Adaptive Cut Selection in Mixed-Integer Linear Programming Open Journal of Mathematical Optimization Mixed-Integer Linear Programming Cutting Plane Selection Instance-Dependent Learning |
| title | Adaptive Cut Selection in Mixed-Integer Linear Programming |
| title_full | Adaptive Cut Selection in Mixed-Integer Linear Programming |
| title_fullStr | Adaptive Cut Selection in Mixed-Integer Linear Programming |
| title_full_unstemmed | Adaptive Cut Selection in Mixed-Integer Linear Programming |
| title_short | Adaptive Cut Selection in Mixed-Integer Linear Programming |
| title_sort | adaptive cut selection in mixed integer linear programming |
| topic | Mixed-Integer Linear Programming Cutting Plane Selection Instance-Dependent Learning |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.25/ |
| work_keys_str_mv | AT turnermark adaptivecutselectioninmixedintegerlinearprogramming AT kochthorsten adaptivecutselectioninmixedintegerlinearprogramming AT serranofelipe adaptivecutselectioninmixedintegerlinearprogramming AT winklermichael adaptivecutselectioninmixedintegerlinearprogramming |