Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems

Chendi Qian, Didier Chételat, Christopher Morris
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:1432-1440, 2024.

Abstract

Recently, machine learning, particularly message-passing graph neural networks (MPNNs), has gained traction in enhancing exact optimization algorithms. For example, MPNNs speed up solving mixed-integer optimization problems by imitating computational intensive heuristics like strong branching, which entails solving multiple linear optimization problems (LPs). Despite the empirical success, the reasons behind MPNNs’ effectiveness in emulating linear optimization remain largely unclear. Here, we show that MPNNs can simulate standard interior-point methods for LPs, explaining their practical success. Furthermore, we highlight how MPNNs can serve as a lightweight proxy for solving LPs, adapting to a given problem instance distribution. Empirically, we show that MPNNs solve LP relaxations of standard combinatorial optimization problems close to optimality, often surpassing conventional solvers and competing approaches in solving time.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-qian24a, title = {Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems}, author = {Qian, Chendi and Ch\'{e}telat, Didier and Morris, Christopher}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {1432--1440}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/qian24a/qian24a.pdf}, url = {https://proceedings.mlr.press/v238/qian24a.html}, abstract = {Recently, machine learning, particularly message-passing graph neural networks (MPNNs), has gained traction in enhancing exact optimization algorithms. For example, MPNNs speed up solving mixed-integer optimization problems by imitating computational intensive heuristics like strong branching, which entails solving multiple linear optimization problems (LPs). Despite the empirical success, the reasons behind MPNNs’ effectiveness in emulating linear optimization remain largely unclear. Here, we show that MPNNs can simulate standard interior-point methods for LPs, explaining their practical success. Furthermore, we highlight how MPNNs can serve as a lightweight proxy for solving LPs, adapting to a given problem instance distribution. Empirically, we show that MPNNs solve LP relaxations of standard combinatorial optimization problems close to optimality, often surpassing conventional solvers and competing approaches in solving time.} }
Endnote
%0 Conference Paper %T Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems %A Chendi Qian %A Didier Chételat %A Christopher Morris %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-qian24a %I PMLR %P 1432--1440 %U https://proceedings.mlr.press/v238/qian24a.html %V 238 %X Recently, machine learning, particularly message-passing graph neural networks (MPNNs), has gained traction in enhancing exact optimization algorithms. For example, MPNNs speed up solving mixed-integer optimization problems by imitating computational intensive heuristics like strong branching, which entails solving multiple linear optimization problems (LPs). Despite the empirical success, the reasons behind MPNNs’ effectiveness in emulating linear optimization remain largely unclear. Here, we show that MPNNs can simulate standard interior-point methods for LPs, explaining their practical success. Furthermore, we highlight how MPNNs can serve as a lightweight proxy for solving LPs, adapting to a given problem instance distribution. Empirically, we show that MPNNs solve LP relaxations of standard combinatorial optimization problems close to optimality, often surpassing conventional solvers and competing approaches in solving time.
APA
Qian, C., Chételat, D. & Morris, C.. (2024). Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:1432-1440 Available from https://proceedings.mlr.press/v238/qian24a.html.

Related Material