MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization
This addresses the problem of local optima entrapment and redundant exploration in NCO for researchers and practitioners, representing an incremental improvement through a novel memory module.
The paper tackles inefficient search space exploration in Neural Combinatorial Optimization (NCO) by introducing MARCO, a memory-augmented reinforcement framework that stores and retrieves optimization data to guide decisions, resulting in diverse, higher-quality solutions for problems like maximum cut and traveling salesman with low computational cost.
Neural Combinatorial Optimization (NCO) is an emerging domain where deep learning techniques are employed to address combinatorial optimization problems as a standalone solver. Despite their potential, existing NCO methods often suffer from inefficient search space exploration, frequently leading to local optima entrapment or redundant exploration of previously visited states. This paper introduces a versatile framework, referred to as Memory-Augmented Reinforcement for Combinatorial Optimization (MARCO), that can be used to enhance both constructive and improvement methods in NCO through an innovative memory module. MARCO stores data collected throughout the optimization trajectory and retrieves contextually relevant information at each state. This way, the search is guided by two competing criteria: making the best decision in terms of the quality of the solution and avoiding revisiting already explored solutions. This approach promotes a more efficient use of the available optimization 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 exploration. Empirical evaluations, carried out on the maximum cut, maximum independent set and travelling salesman problems, reveal that the memory module effectively increases the exploration, enabling 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.