Learning to Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning

Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, Chris Maddison
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:17584-17600, 2022.

Abstract

Cutting planes are essential for solving mixed-integer linear problems (MILPs), because they facilitate bound improvements on the optimal solution value. For selecting cuts, modern solvers rely on manually designed heuristics that are tuned to gauge the potential effectiveness of cuts. We show that a greedy selection rule explicitly looking ahead to select cuts that yield the best bound improvement delivers strong decisions for cut selection – but is too expensive to be deployed in practice. In response, we propose a new neural architecture (NeuralCut) for imitation learning on the lookahead expert. Our model outperforms standard baselines for cut selection on several synthetic MILP benchmarks. Experiments on a realistic B&C solver further validate our approach, and exhibit the potential of learning methods in this setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-paulus22a, title = {Learning to Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning}, author = {Paulus, Max B and Zarpellon, Giulia and Krause, Andreas and Charlin, Laurent and Maddison, Chris}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {17584--17600}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/paulus22a/paulus22a.pdf}, url = {https://proceedings.mlr.press/v162/paulus22a.html}, abstract = {Cutting planes are essential for solving mixed-integer linear problems (MILPs), because they facilitate bound improvements on the optimal solution value. For selecting cuts, modern solvers rely on manually designed heuristics that are tuned to gauge the potential effectiveness of cuts. We show that a greedy selection rule explicitly looking ahead to select cuts that yield the best bound improvement delivers strong decisions for cut selection – but is too expensive to be deployed in practice. In response, we propose a new neural architecture (NeuralCut) for imitation learning on the lookahead expert. Our model outperforms standard baselines for cut selection on several synthetic MILP benchmarks. Experiments on a realistic B&C solver further validate our approach, and exhibit the potential of learning methods in this setting.} }
Endnote
%0 Conference Paper %T Learning to Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning %A Max B Paulus %A Giulia Zarpellon %A Andreas Krause %A Laurent Charlin %A Chris Maddison %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-paulus22a %I PMLR %P 17584--17600 %U https://proceedings.mlr.press/v162/paulus22a.html %V 162 %X Cutting planes are essential for solving mixed-integer linear problems (MILPs), because they facilitate bound improvements on the optimal solution value. For selecting cuts, modern solvers rely on manually designed heuristics that are tuned to gauge the potential effectiveness of cuts. We show that a greedy selection rule explicitly looking ahead to select cuts that yield the best bound improvement delivers strong decisions for cut selection – but is too expensive to be deployed in practice. In response, we propose a new neural architecture (NeuralCut) for imitation learning on the lookahead expert. Our model outperforms standard baselines for cut selection on several synthetic MILP benchmarks. Experiments on a realistic B&C solver further validate our approach, and exhibit the potential of learning methods in this setting.
APA
Paulus, M.B., Zarpellon, G., Krause, A., Charlin, L. & Maddison, C.. (2022). Learning to Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:17584-17600 Available from https://proceedings.mlr.press/v162/paulus22a.html.

Related Material