Learning to Remove Cuts in Integer Linear Programming

Pol Puigdemont, Stratis Skoulakis, Grigorios Chrysos, Volkan Cevher
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:41235-41255, 2024.

Abstract

Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional optimal solution while not affecting the optimal integer solution. In this work, we explore a novel approach within cutting plane methods: instead of only adding new cuts, we also consider the removal of previous cuts introduced at any of the preceding iterations of the method under a learnable parametric criteria. We demonstrate that in fundamental combinatorial optimization settings such cut removal policies can lead to significant improvements over both human-based and machine learning-guided cut addition policies even when implemented with simple models.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-puigdemont24a, title = {Learning to Remove Cuts in Integer Linear Programming}, author = {Puigdemont, Pol and Skoulakis, Stratis and Chrysos, Grigorios and Cevher, Volkan}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {41235--41255}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/puigdemont24a/puigdemont24a.pdf}, url = {https://proceedings.mlr.press/v235/puigdemont24a.html}, abstract = {Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional optimal solution while not affecting the optimal integer solution. In this work, we explore a novel approach within cutting plane methods: instead of only adding new cuts, we also consider the removal of previous cuts introduced at any of the preceding iterations of the method under a learnable parametric criteria. We demonstrate that in fundamental combinatorial optimization settings such cut removal policies can lead to significant improvements over both human-based and machine learning-guided cut addition policies even when implemented with simple models.} }
Endnote
%0 Conference Paper %T Learning to Remove Cuts in Integer Linear Programming %A Pol Puigdemont %A Stratis Skoulakis %A Grigorios Chrysos %A Volkan Cevher %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-puigdemont24a %I PMLR %P 41235--41255 %U https://proceedings.mlr.press/v235/puigdemont24a.html %V 235 %X Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional optimal solution while not affecting the optimal integer solution. In this work, we explore a novel approach within cutting plane methods: instead of only adding new cuts, we also consider the removal of previous cuts introduced at any of the preceding iterations of the method under a learnable parametric criteria. We demonstrate that in fundamental combinatorial optimization settings such cut removal policies can lead to significant improvements over both human-based and machine learning-guided cut addition policies even when implemented with simple models.
APA
Puigdemont, P., Skoulakis, S., Chrysos, G. & Cevher, V.. (2024). Learning to Remove Cuts in Integer Linear Programming. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:41235-41255 Available from https://proceedings.mlr.press/v235/puigdemont24a.html.

Related Material