MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization
(2024) Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24} — Location: Jeju, South Korea (19.August.2023)
Files
0766.pdf
Open Access - Adobe PDF
- 488.93 KB
Details
- Authors
- Abstract
- Neural Combinatorial Optimization (NCO) is an emerging domain where deep learning techniques are employed to address combinatorial optimiza- tion problems as a standalone solver. Despite their potential, existing NCO methods often suf- fer from inefficient search space exploration, fre- quently leading to local optima entrapment or re- dundant exploration of previously visited states. This paper introduces a versatile framework, re- ferred to as Memory-Augmented Reinforcement for Combinatorial Optimization (MARCO), that can be used to enhance both constructive and im- provement methods in NCO through an innova- tive memory module. MARCO stores data col- lected throughout the optimization trajectory and retrieves contextually relevant information at each state. This way, the search is guided by two com- peting criteria: making the best decision in terms of the quality of the solution and avoiding revisit- ing already explored solutions. This approach pro- motes a more efficient use of the available opti- mization budget. Moreover, thanks to the parallel nature of NCO models, several search threads can run simultaneously, all sharing the same memory module, enabling an efficient collaborative explo- ration. Empirical evaluations, carried out on the maximum cut, maximum independent set and trav- elling salesman problems, reveal that the memory module effectively increases the exploration, en- abling the model to discover diverse, higher-quality solutions. MARCO achieves good performance in a low computational cost, establishing a promising new direction in the field of NCO.
- Affiliations
Citations
Garmendia, A. I., Cappart, Q., Ceberio, J., & Mendiburu, A. (2024). MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24). Published. Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24}, Jeju, South Korea. https://doi.org/10.24963/ijcai.2024/766 (Original work published 2024)