Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning

Taoan Huang, Aaron M Ferber, Yuandong Tian, Bistra Dilkina, Benoit Steiner
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:13869-13890, 2023.

Abstract

Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high-quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a more efficient one with contrastive learning. We use graph attention networks and a richer set of features to further improve its performance.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-huang23g, title = {Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning}, author = {Huang, Taoan and Ferber, Aaron M and Tian, Yuandong and Dilkina, Bistra and Steiner, Benoit}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {13869--13890}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/huang23g/huang23g.pdf}, url = {https://proceedings.mlr.press/v202/huang23g.html}, abstract = {Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high-quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a more efficient one with contrastive learning. We use graph attention networks and a richer set of features to further improve its performance.} }
Endnote
%0 Conference Paper %T Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning %A Taoan Huang %A Aaron M Ferber %A Yuandong Tian %A Bistra Dilkina %A Benoit Steiner %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-huang23g %I PMLR %P 13869--13890 %U https://proceedings.mlr.press/v202/huang23g.html %V 202 %X Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high-quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a more efficient one with contrastive learning. We use graph attention networks and a richer set of features to further improve its performance.
APA
Huang, T., Ferber, A.M., Tian, Y., Dilkina, B. & Steiner, B.. (2023). Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:13869-13890 Available from https://proceedings.mlr.press/v202/huang23g.html.

Related Material