Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization
(2021) The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)
Files
16484-ArticleText-19978-1-2-20210518.pdf
Open Access - Adobe PDF
- 241.24 KB
Details
- Authors
- Abstract
- Combinatorial optimization has found applications in numer- ous fields, from aerospace to transportation planning and eco- nomics. The goal is to find an optimal solution among a finite set of possibilities. The well-known challenge one faces with combinatorial optimization is the state-space explosion prob- lem: the number of possibilities grows exponentially with the problem size, which makes solving intractable for large prob- lems. In the last years, deep reinforcement learning (DRL) has shown its promise for designing good heuristics dedicated to solve NP-hard combinatorial optimization problems. However, current approaches have an important shortcoming: they only provide an approximate solution with no systematic ways to improve it or to prove optimality. In another context, constraint programming (CP) is a generic tool to solve combinatorial optimization problems. Based on a complete search procedure, it will always find the optimal solution if we allow an execu- tion time large enough. A critical design choice, that makes CP non-trivial to use in practice, is the branching decision, directing how the search space is explored. In this work, we propose a general and hybrid approach, based on DRL and CP, for solving combinatorial optimization problems. The core of our approach is based on a dynamic programming formulation, that acts as a bridge between both techniques. We experimen- tally show that our solver is efficient to solve three challenging problems: the traveling salesman problem with time windows, the 4-moments portfolio optimization problem, and the 0-1 knapsack problem. Results obtained show that the framework introduced outperforms the stand-alone RL and CP solutions, while being competitive with industrial solvers.
- Affiliations
Citations
Cappart, Q., Moisan, T., Rousseau, L.-M., Prémont-Schwarz, I., & Cire, A. A. (2021). Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3677-3687. https://doi.org/10.1609/aaai.v35i5.16484 (Original work published 2021)