Neural method improves large scale optimization by reusing solution memory
MiLoop: Selective Memory Propagation for Neural Combinatorial Optimization
Machine Learning
Summary
Finding the best solution for large, complex problems can take a lot of time. The authors developed a method called MiLoop that helps a neural network remember past steps while building solutions, so it doesn't start from scratch each time. This approach allows the method to learn better over time without needing extra labels or complicated training tricks. Tests showed MiLoop works well on very large problems, even with millions of parts to arrange.
What this means in practice
- •For logistics planners: Solve large routing and scheduling problems faster by using memory-enhanced neural methods for better stepwise decision making.
- •For chip design engineers: Optimize large-scale circuit layouts efficiently by reusing partial solutions in neural combinatorial models to improve solution quality.
Authors
Changliang Zhou, Yuanyao Chen, Rongsheng Chen, Zhiyun Lin, Zhenkun Wang
Abstract
Constructive neural combinatorial optimization (NCO) has emerged as a promising paradigm that learns to construct solutions to combinatorial optimization problems (COPs) step by step, which reduces reliance on handcrafted rules and enables fast inference. While many methods with dynamic embeddings generalize well, they typically rebuild subproblem representations from scratch at each step using deep attention stacks. Many high-performing methods in this category rely on solution labels or pseudo-labels for efficient training, or on aggressive search space pruning during reinforcement learning (RL). To address these limitations, we propose Memory-in-the-Loop (MiLoop), a purely RL-based constructive framework that leverages the multi-step computation already required by a rollout for selective memory propagation. Each rollout provides solution-quality feedback for learning while propagating historical representations, thereby enabling a shallow policy to learn effective dynamic embeddings without external solution labels or training-time search-space pruning. Specifically, MiLoop fuses current embeddings with historical memory before the attention layers and applies adaptive gated updates afterward. The updated representations support both current decisions and stepwise reuse. Extensive experiments across four COPs demonstrate that MiLoop consistently produces high-quality solutions on instances ranging from 100 to 10 million nodes, highlighting its strong generalization ability.