Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates
DOI:
https://doi.org/10.1609/aaai.v38i18.30067Keywords:
SO: Combinatorial Optimization, ML: Reinforcement Learning, PRS: Mixed Discrete/Continuous Planning, PRS: Planning under Uncertainty, PRS: Scheduling under Uncertainty, SO: Algorithm Configuration, SO: Mixed Discrete/Continuous Search, SO: Sampling/Simulation-based SearchAbstract
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.Downloads
Published
2024-03-24
How to Cite
Mana, K., Acero, F., Mak, S., Zehtabi, P., Cashmore, M., Magazzeni, D., & Veloso, M. (2024). Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18), 20786-20793. https://doi.org/10.1609/aaai.v38i18.30067
Issue
Section
AAAI Technical Track on Search and Optimization