MiLoop: Selective Memory Propagation for Neural Combinatorial Optimization

Changliang Zhou; Yuanyao Chen; Rongsheng Chen; Zhiyun Lin; Zhenkun Wang

cs.LGOct 1, 2026

MiLoop: Selective Memory Propagation for Neural Combinatorial Optimization

Authors: Changliang Zhou, Yuanyao Chen, Rongsheng Chen, Zhiyun Lin, Zhenkun Wang

Organizations: School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China · Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, Southern University of Science and Technology, Shenzhen, China · Pengcheng Laboratory, Shenzhen, China

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.

Figures & tables

Figure 1: Comparison of different embeddings. Unlike traditional dynamic embeddings, MiLoop maintains a trajectory memory throughout each rollout, with selective updates for subsequent reuse.

Figure 2: Overview of MiLoop, illustrated on the TSP instances, the starting node

\pi_{1}

is randomly selected at the first step. During RL rollouts, MiLoop fuses node-wise memory with current embeddings before attention and selectively updates it afterward for action scoring and cross-step reuse.

Method	TSP100			TSP1K			TSP5K			TSP10K
Method	Obj.	Gap	Time	Obj.	Gap	Time	Obj.	Gap	Time	Obj.	Gap	Time
LKH3	7.76	0.00%	0.34s	23.12	0.00%	1.7m	50.97	0.00%	12m	71.78	0.00%	33m
Concorde	7.76	0.00%	0.36s	23.12	0.00%	1m	50.95	-0.05%	31m	72.00	0.15%	1.4h
H-TSP	$-$	$-$	$-$	24.66	6.66%	48s	55.16	8.21%	1.2m	77.75	8.38%	2.2m
UDC- $x_{50}(\alpha=50)$	7.78	0.32%	0.49s	23.53	1.78%	2.92s	54.25	6.43%	0.77s	OOM
GLOP	7.76	0.05%	0.5s	23.78	2.85%	10.2s	53.15	4.26%	1.0m	75.04	4.39%	1.9m

Table 1: Comparison of TSP and CVRP instances with uniform distribution (100

\leq N\leq

10K).

Method	TSPLIB					CVRPLIB
Method	(0,1K]	(1K, 5K]	(5K, 100K)	All	Solved #	(0,1K]	(1K, 7K]	(7K,30K]	All	Solved #
UDC α=50	4.28%	11.89%	24.81%	7.13% $\dagger$	73/81	7.12%	14.06%	OOM	7.33% $\dagger$	103/110
GLOP	5.55%	12.92%	11.99%	8.35%	81/81	18.86%	19.89%	24.42%	19.20%	110/110
Omni-VRP aug $\times$ 8	13.04%	39.14%	79.65%	26.38% $\dagger$	78/81	11.89%	165.02%	223.03%	21.65% $\dagger$	106/110
ELG aug $\times$ 8	3.13%	11.13%	OOM	5.53% $\dagger$	70/81	6.03%	16.37%	OOM	6.23% $\dagger$	102/110
ICAM aug $\times$ 8	3.89%	14.23%	17.52%	7.52% $\dagger$	74/81	6.21%	16.86%	OOM	6.62% $\dagger$	104/110

Table 2: Comparison on TSPLib (

0\textless N\leq 85,900

) and CVRPLib instances (

0\textless N\leq 30,000

Instance	LEHD	INViT	L2R	MiLoop
E10k.0	24.63%	6.64%	4.56%	1.90%
E10k.1	26.51%	7.08%	4.59%	2.28%
E10k.2	24.74%	7.38%	4.77%	2.92%
E31k.0	OOM	6.97%	4.82%	4.18%
E31k.1	OOM	7.22%	4.74%	2.42%
E100k.0	OOM	OOM	4.71%	2.52%

Table 3: Comparison on ultra-large-scale TSP instances (greedy decoding).

Input Fusion		Gated Update	TSP100	TSP1K
RSE	MiLoop	Gated Update	Gap	Gap
$\checkmark$	$\times$	$\times$	0.88%	9.17%
$\times$	$\checkmark$	$\times$	1.17%	2.90%
$\times$	$\checkmark$	$\checkmark$	0.84%	1.90%

Table 4: Comparison of different recurrent embeddings.

Figure 3: Cosine similarity of node embeddings during TSP construction for a traditional dynamic-embedding model variant and MiLoop. We use the adjacent step or the first step as the reference.

Memory		Looped	Attention	Train	TSP100		TSP1K		TSP10K
Fusion	Update	Embedding	Layers	Train	Obj. (Gap)	Time	Obj. (Gap)	Time	Obj. (Gap)	Time
$\checkmark$	$\times$	$\checkmark$	3	DPO	7.85 (1.17%)	0.004s	23.79 (2.90%)	0.9s	74.24 (3.43%)	2.96s
$\times$	$\checkmark$	$\checkmark$	3	DPO	7.90 (1.79%)	0.004s	24.95 (7.93%)	0.9s	78.86 (9.98%)	2.96s
$\times$	$\times$	$\times$	3	DPO	7.88 (1.61%)	0.004s	24.64 (6.59%)	0.9s	75.82 (5.63%)	2.96s
$\times$	$\times$	$\times$	6	DPO	7.85 (1.18%)	0.008s	24.45 (5.78%)	1.72s	74.93 (4.39%)	5.84s
$\checkmark$	$\checkmark$	$\checkmark$	3	RF	7.86 (1.26%)	0.004s	24.23 (4.81%)	0.89s	74.85 (4.28%)	2.96s

Table 5: Ablation study of MiLoop on TSP. RF denotes REINFORCE algorithm ( Williams, 1992 ) .

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Problem / dataset	Size $N$	# instances	Capacity / details
Synthetic test sets
TSP	$100$	$10{,}000$	—
	$1\mathrm{K}$	$128$
	$5\mathrm{K},\,10\mathrm{K}$	$16$
CVRP	$100$	$10{,}000$	$C=50$
	$1\mathrm{K}$	$128$	$C=50$

Appendix

Table 6: Summary of the test datasets and evaluation settings.

Model settings
Setting	TSP	CVRP	PDTSP	KP
Embedding dimension $d$	$128$
Feed-forward hidden dimension	$512$
Number of attention layers $L$	$3$
Attention mechanism	AAFM ( Zhou et al., 2026a )
Logit clipping parameter $\xi$	$10$

Appendix

Table 7: Model and training settings of MiLoop.

Similarity measure	Traditional dynamic embedding	MiLoop
Adjacent steps ( $C_{t,i}$ )	0.8480	0.9159
First recorded step ( $A_{t,i}$ )	0.7655	0.4497

Appendix

Table 8: Mean cosine similarities of adjacent steps and first-recorded step.

Panel of Figure 4 — Figure 4: Node-representation similarity during greedy TSP100 construction. The left column shows MiLoop and the right column shows the traditional dynamic-embedding baseline. Figures (a,b) report adjacent-step cosine $C_{t,i}$ ; Figures (c,d) report cosine to the first recorded representation $A_{t,i}$ . Within each heatmap, rows correspond to autoregressive construction steps, and columns correspond to the nodes that remain unvisited at that step. Colors closer to yellow indicate higher similarity, while colors closer to green indicate lower similarity. As construction proceeds, visited nodes drop out of subsequent comparisons, producing the shrinking triangular region; the unvisited set is exhausted when the tour is complete. Gray entries indicate visited nodes or undefined similarities.

Figure 5: Tour comparisons between MiLoop (left) and the traditional dynamic embedding (right) on TSP100 (top) and TSP1000 (bottom). Solid blue and orange lines depict the tours produced by MiLoop and the baseline, respectively. Black dots denote nodes, and stars mark the starting nodes.

Method	PDTSP100			PDTSP200			PDTSP500			PDTSP1000
Method	Obj.	Gap	Time	Obj.	Gap	Time	Obj.	Gap	Time	Obj.	Gap	Time
LKH3	9.43	0.00%	5.88s	13.47	0.00%	28.26s	21.54	0.00%	2.06m	31.24	0.00%	5.86m
Heter-AM $\dagger$	10.35	9.76%	0.002s	$-$	$-$	$-$	$-$	$-$	$-$	$-$	$-$
URS aug $\times$ 8	9.90	4.98%	0.004s	14.47	7.42%	0.05s	24.27	12.67%	0.38s	35.92	14.98%	2.87s
MiLoop greedy	9.86	4.56%	0.005s	13.75	2.09%	0.02s	21.92	1.74%	0.16s	31.98	2.40%	1.09s
MiLoop ( $M=100$ )	9.68	2.67%	0.292s	13.51	0.29%	1.37s	21.48	-0.27%	15.17s	31.14	-0.35%	1.75m

Appendix

Table 9: Comparison on PDTSP instances with

N\leq 1{,}000

	Capacity	OR-Tools	POMO (all Trajec.)			BQ (greedy)			MiLoop (greedy)
	Capacity	Value	Value	Gap	Time	Value	Gap	Time	Value	Gap	Time
KP200	C=10	36.0240	34.9182	3.070%	1s	35.9136	0.309%	4s	35.9559	0.189%	2s
	C=25	57.1729	57.1646	0.014%	1s	57.1184	0.096%	4s	57.1271	0.080%	3s
	C=50	80.7133	79.8295	1.095%	1s	80.1901	0.650%	5s	80.6814	0.040%	3s
	C=100	99.4987	99.2055	0.295%	1s	99.4338	0.065%	5s	99.4945	0.004%	4s
KP500	C=10	57.4130	54.3516	5.332%	3s	56.8149	1.045%	21s	57.2083	0.357%	3s

Appendix

Table 10: Comparison on KP with scale

\leq 1,000

across different capacity settings.

Instance	Scale	BQ greedy	LEHD greedy	SIGD greedy	L2C-Insert greedy	INViT-3V greedy	L2R greedy	Rec-NCO greedy	MiLoop greedy	MiLoop ( $M=100$ )
eil51	51	0.94%	1.17%	0.47%	0.94%	3.99%	0.70%	1.41%	2.82%	0.00%
berlin52	52	0.00%	0.00%	0.00%	0.01%	9.64%	0.77%	0.00%	0.00%	0.00%
st70	70	0.00%	0.00%	0.59%	0.15%	2.37%	0.30%	0.00%	1.63%	0.00%
eil76	76	0.00%	1.49%	0.56%	0.56%	5.76%	3.53%	0.93%	0.19%	0.00%
pr76	76	0.92%	0.22%	0.14%	1.62%	5.90%	2.76%	0.79%	1.24%	0.02%
rat99	99	0.58%	0.58%	0.17%	0.00%	7.68%	4.54%	1.57%	2.56%	0.00%

Appendix

Table 11: Detail results on TSPLIB: Constructive NCO with Dynamic Embeddings.

Instance	Scale	BQ greedy	LEHD greedy	SIGD greedy	L2C-Insert greedy	INViT-3V greedy	L2R greedy	Rec-NCO greedy	MiLoop greedy	MiLoop ( $M=100$ )
Set-X
X-n101-k25	100	9.62%	13.98%	13.85%	7.71%	12.24%	10.30%	20.96%	5.50%	4.22%
X-n106-k14	105	4.44%	3.73%	2.60%	3.41%	4.97%	3.65%	5.17%	3.69%	2.74%
X-n110-k13	109	4.86%	1.83%	2.33%	2.42%	7.63%	5.41%	3.99%	2.71%	0.81%
X-n115-k10	114	21.84%	9.39%	23.79%	11.80%	12.58%	18.22%	21.92%	3.58%	3.49%
X-n120-k6	119	3.19%	3.89%	2.60%	2.51%	12.83%	7.16%	2.75%	3.00%	1.04%

Appendix

Table 12: Detail results on CVRPLIB: Constructive NCO with Dynamic Embeddings.

Figure 6: Solution visualizations on synthetic TSP instances. Rows show TSP100, TSP1000, and TSP10000, while columns show LKH3, MiLoop, L2R, and LEHD, respectively. All methods solve the same instance within each row. Gray dashed lines overlay the LKH3 reference tour, and stars mark the starting node. Each panel reports the tour length and its gap relative to the LKH3 solution. All results are obtained via greedy decoding.

Figure 7: Solution visualizations on synthetic CVRP instances. Rows show CVRP100, CVRP1000, and CVRP10000. The first column shows the reference solutions, obtained by HGS; the remaining columns show MiLoop, L2R, and LEHD, respectively. All methods solve the same instance within each row. Gray dashed lines overlay the reference routes, and stars mark the depot. Each panel reports the total route length and its gap relative to the reference solution. All results are obtained via greedy decoding.

Panel of Figure 8 — Figure 8: Solution visualizations on TSPLib (left) and CVRPLib (right), ordered by increasing instance size within each column. Red lines show solution edges, and black squares mark CVRP depots. Instance names, sizes, and gaps are given in the subcaptions. All results are obtained via greedy decoding.

Resource	Type	Link	License / usage terms
Concorde	Code	https://www.math.uwaterloo.ca/tsp/concorde.html	Academic research use
OR-Tools	Code	https://github.com/google/or-tools	Apache-2.0
LKH3	Code	http://webhotel4.ruc.dk/~keld/research/LKH-3/	Academic and non-commercial use
HGS	Code	https://github.com/vidalt/HGS-CVRP	MIT
POMO	Code	https://github.com/yd-kwon/POMO	MIT
Omni-VRP	Code	https://github.com/RoyalSkye/Omni-VRP	MIT

Appendix

Table 13: Licenses and stated usage terms of baseline code and benchmark datasets.

Explore similar work

Sep 5, 2025cs.LG

Recurrent State Encoders for Efficient Neural Combinatorial Optimization

The primary paradigm in Neural Combinatorial Optimization (NCO) consists of construction methods, where a neural network is trained to sequentially add one solution component at a time until a complete solution is formed. We observe that the typical changes to the state between two steps are small, since usually only the node added to the solution is removed from the state. An efficient model should be able to reuse computation from prior steps. To that end, we propose a recurrent encoder that computes state embeddings based not only on the current state but also on embeddings from the previous state. We show that this recurrent encoder can achieve equivalent or better performance than a non-recurrent encoder even with

3\times

fewer layers, thus significantly improving latency. We demonstrate our findings on three different problems: the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Orienteering Problem (OP), and integrate the models into a large neighborhood search algorithm to showcase the practical relevance of our findings.

Tim Dernedde, Daniela Thyssens, Lars Schmidt-Thieme

Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim

Neural Combinatorial Optimization Vehicle Routing Problem Recurrent State Neural Network Optimization

Ask PDF

May 22, 2024cs.LG

Leader Reward for POMO-Based Neural Combinatorial Optimization

Deep neural networks based on reinforcement learning (RL) for solving combinatorial optimization (CO) problems are developing rapidly and have shown a tendency to approach or even outperform traditional solvers. However, existing methods overlook an important distinction: CO problems differ from other traditional problems in that they focus solely on the optimal solution provided by the model within a specific length of time, rather than considering the overall quality of all solutions generated by the model. In this paper, we propose Leader Reward and apply it during two different training phases of the Policy Optimization with Multiple Optima (POMO) model to enhance the model's ability to generate optimal solutions. This approach is applicable to a variety of CO problems, such as the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Flexible Flow Shop Problem (FFSP), but also works well with other POMO-based models or inference phase's strategies. We demonstrate that Leader Reward greatly improves the quality of the optimal solutions generated by the model. Specifically, we reduce the POMO's gap to the optimum by more than 100 times on TSP100 with almost no additional computational overhead.

Chaoyang Wang, Pengzhi Cheng, Jingze Li +1

Fudan University

Neural Combinatorial Optimization Combinatorial Optimization Vehicle Routing Problem Neural Network Optimization Reward Signal

Ask PDF

Jul 30, 2026cs.LG

AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization

Combinatorial optimization problems (COPs) underpin many real-world decisions, but their exponentially large search spaces make high-quality solutions costly to obtain. Neural combinatorial optimization (NCO) learns fast construction policies, typically with reinforcement learning (RL), while preference-based NCO improves sample efficiency by learning from relative solution quality. However, existing preference objectives combine two distinct design choices in manually specified, one-size-fits-all formulations: what learning signal to extract from each solution pair and how to weight each pair relative to the sampled set. We present AutoPref, the first LLM-guided framework for automated preference-objective discovery in NCO. AutoPref factorizes the objective into a pairwise loss program, which defines the learning signal, and a set-aware weighting program, which determines each pair's relative contribution. Their composition forms a unified programmatic objective space containing existing preference objectives as special cases. To make its search tractable, we introduce a staged conditional search strategy with behavioral gates that filter inadmissible programs before short-horizon training and evaluation. Across TSP, CVRP, FFSP, and JSSP, AutoPref consistently outperforms strong hand-designed baselines across problem scales, demonstrating the benefits and scalability of automated objective discovery for NCO.

Shengda Gu, Kai Li, Xinyi Ke +3

C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Tencent AI Lab +1

Neural Combinatorial Optimization Self

Ask PDF