Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates
Kyle Mana, Fernando Acero, Stephen Mak, Parisa Zehtabi, Michael Cashmore, Daniele Magazzeni, Manuela Veloso
Abstract
Discrete optimization belongs to the set of N P-hard problems, spanning fields such as mixed-integer programming and combinatorial optimization. A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms, which reach optimal solutions by iteratively adding inequalities known as cuts to refine a feasible set. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. In this work, we propose a method for accelerating cutting-plane algorithms via reinforcement learning. Our approach uses learned policies as surrogates for N P-hard elements of the cut generating procedure in a way that (i) accelerates convergence, and (ii) retains guarantees of optimality. We apply our method on two types of problems where cutting-plane algorithms are commonly used: stochastic optimization, and mixed-integer quadratic programming. We observe the benefits of our method when applied to Benders decomposition (stochastic optimization) and iterative loss approximation (quadratic programming), achieving up to 45% faster average convergence when compared to modern alternative algorithms.
BibTeX
@article{Mana_Acero_Mak_Zehtabi_Cashmore_Magazzeni_Veloso_2024, title={Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/30067}, DOI={10.1609/aaai.v38i18.30067}, abstractNote={Discrete optimization belongs to the set of N P-hard
problems, spanning fields such as mixed-integer
programming and combinatorial optimization. A current
standard approach to solving convex discrete optimization
problems is the use of cutting-plane algorithms, which
reach optimal solutions by iteratively adding inequalities
known as cuts to refine a feasible set. Despite the existence
of a number of general-purpose cut-generating algorithms,
large-scale discrete optimization problems continue to suffer
from intractability. In this work, we propose a method for
accelerating cutting-plane algorithms via reinforcement
learning. Our approach uses learned policies as surrogates
for N P-hard elements of the cut generating procedure
in a way that (i) accelerates convergence, and (ii) retains
guarantees of optimality. We apply our method on two types
of problems where cutting-plane algorithms are commonly
used: stochastic optimization, and mixed-integer quadratic
programming. We observe the benefits of our method when
applied to Benders decomposition (stochastic optimization)
and iterative loss approximation (quadratic programming),
achieving up to 45% faster average convergence when
compared to modern alternative algorithms.}, number={18}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Mana, Kyle and Acero, Fernando and Mak, Stephen and Zehtabi, Parisa and Cashmore, Michael and Magazzeni, Daniele and Veloso, Manuela}, year={2024}, month={Mar.}, pages={20786-20793} }