acceptodds
Under review as a conference paper at ICLR 2027

ARC: Assignment-Structured Representation and Construction for Asymmetric TSP

Abstract

Neural constructive solvers efficiently generate tours for the asymmetric traveling salesman problem (ATSP), but maintaining solution quality beyond the training scale remains challenging. With direction-dependent costs, a cheap move to one node may force another node to use an expensive alternative. This competition arises because each node in a tour must have exactly one predecessor and one successor. Assignment captures this requirement through a one-to-one pairing of source and destination nodes, providing a global reference for local choices. When this structure remains implicit, neural policies must infer the changing competition from learned representations and tour states, even at unseen scales. We propose ARC (Assignment-structured Representation and Construction), which uses assignment structure both to represent directed costs and to guide tour construction. ARC derives source and destination dual potentials and gauge-adjusted edge costs from a full-instance assignment decomposition, providing complementary node and edge inputs. The adjustment shifts every complete tour's cost by the same constant, preserving which tours are cheaper. As construction proceeds, ARC updates a pressure signal for each remaining destination through residual assignment rebalancing. Frontier Sinkhorn Pressure (FSP) uses these signals to guide choices without fully solving the remaining assignment problem at every step. Experiments show that ARC outperforms the evaluated neural baselines on standard ATSP benchmarks and generalizes to larger unseen instances. Structured inputs reduce reliance on many starts, while FSP improves policies without retraining.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Asymmetric Traveling Salesman Problem

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_yTKzOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors propose Assignment-structured Representation and Construction (ARC) for the ATSP. This method builds on Sinkhorn assignment to both provide a structured encoder input and to guide the decoding process. Building on a RADAR base model, the authors show that their method improves cross-size generalization for the ATSP. They also show that the decoding component, referred to as FSP, improves a number of base models without retraining.

Critical strengths
  • Combining the classical optimization principle of ATSP assignment relaxation to construct principled encoder features and a decoding mechanism is a nice and sound contribution that seems effective empirically. The fact that the decoding integrates zero-shot with existing backbones and improves their results is also a major advantage.
  • Thorough experiments, ablations and generalization studies support the major arguments and claimed advantages of ARC.
Critical weaknesses
  • My main criticism is that the empirical study (and to some extent the paper overall) only concerns the ATSP. In general, I believe a narrow problem focus should not be a barrier for acceptance. However, in this case it seems necessary to investigate whether the conclusions hold for more general VRPs. To my understanding, the core assignment operator should transfer rather cleanly to for example the ACVRP and other variants. Some experimental results along these lines and a broader discussion on applicability to other problems would significantly strengthen the paper.
  • The presentation is also quite dense in places, especially in sections 2-3. Relying less on technical jargon and introducing the notation more thoroughly would improve the text substantially.

In particular, if the first point above is addressed satisfactorily, I might be compelled to raise my score. The methodological contribution and experimental evidence are sufficient, but the broader impact is somewhat unclear as the paper stands.

Questions for authors
  • Are there any major obstacles to generalize ARC to other asymmetric VRPs? Are performance advantages maintained in such cases?
6 comments

Thank you for your careful review and constructive suggestions on extending ARC beyond ATSP and improving the clarity of Sections 2–3. In response, we have extended ARC to a multi-task setting covering 16 asymmetric VRP variants and provide the formulation, experimental setup, and results below. We also clarify the notation and streamline the explanations of the method. The corresponding revisions to the main text are highlighted in different colors for ease of reference. We hope these responses and revisions clarify ARC's broader applicability and make the presentation more accessible.

Response to W1 and Q1: Generalization to asymmetric VRPs.

Thank you for this constructive suggestion. We agree that broader VRP experiments would strengthen the evidence for ARC's applicability. We have extended ARC to 16 asymmetric VRP variants, and ARC-T achieves the best solution quality among the evaluated neural methods in all 16.

To extend ARC to VRPs, we adapt the assignment constraints to allow multiple routes to share a depot. Each customer retains unit incoming and outgoing assignment mass. With depot 0 and NN customers, we use a continuous assignment matrix PP satisfying

P1=P⊤1=(κ,1,…,1)⊤.P\mathbf{1}=P^{\top}\mathbf{1}=(\kappa,1,\ldots,1)^{\top}.

The depot mass κ\kappa has the capacity-based lower bound

K_{\mathrm{lb}}=\max\left\\{\left\lceil\frac{\sum_i d_i^{\mathrm{delivery}}}{Q}\right\rceil,\left\lceil\frac{\sum_i d_i^{\mathrm{pickup}}}{Q}\right\rceil,1\right\\},

where QQ is vehicle capacity. We combine Sinkhorn scaling with bisection over κ∈[Klb,N]\kappa\in[K_{\mathrm{lb}},N] to approximately solve the entropy-regularized assignment relaxation and obtain κ\kappa and dual potentials ui,viu_i,v_i. The capacity bound reflects aggregate demand; directed costs also affect route organization. Estimating κ\kappa lets the depot mass adapt to this cost structure through a scalar search. These potentials provide ARC's node and edge features, and FSP guides route construction. The RouteFinder decoder handles each variant's constraints.

To evaluate this extension, we use the RouteFinder (RF) multi-task framework and follow RADAR's experimental setup for the 16 asymmetric VRP variants. These variants cover capacity, open routes, backhauls, route-length limits, time windows, and their combinations. All neural methods use six encoder layers, following the released implementation, and are trained on all 16 variants. We evaluate 15,998 test instances and measure neural runtimes on an A100 GPU. ARC-base uses the assignment representation without FSP; ARC-I adds FSP at inference; ARC-T uses FSP during training and inference.

MethodAvg. Obj. ↓Avg. Gap (%) ↓Avg. Time ↓
HGS2.4275—20.84m
OR-Tools2.46271.541020.84m
RF2.49932.92221.52s
RF-NN2.49972.92251.52s
RADAR2.48522.36052.47s
ARC-base2.47802.04112.66s
ARC-I2.47551.93393.15s
ARC-T2.46331.43143.16s

ARC-T reduces the average gap relative to HGS from RADAR's 2.3605% to 1.4314%, a 39.4% relative reduction, with average runtime increasing from 2.47s to 3.16s. ARC-base improves on RADAR in every variant, reducing the average gap by 13.5% with 0.19s additional runtime. Adding FSP at inference improves every variant further, and training with FSP gives the strongest neural results throughout.

Response to W1 and Q1 (continued). Following the average results reported in our previous comment, we provide the detailed gap and runtime results for each of the 16 asymmetric VRP variants below.

Variant (Gap %/time)HGSOR-ToolsRFRF-NNRADARARC-baseARC-IARC-T
ACVRP—/20.84m2.92/20.84m3.65/1.40s3.45/1.41s3.08/2.35s2.50/2.54s2.29/2.99s1.63/2.99s
AOVRP—/20.84m1.84/20.84m3.39/1.48s3.32/1.49s2.91/2.43s2.47/2.63s2.30/3.09s1.77/3.10s
AVRPB—/20.84m2.61/20.84m4.20/1.40s4.22/1.40s3.48/2.35s3.06/2.54s2.93/2.99s2.11/2.99s
AVRPL—/20.84m3.02/20.84m3.64/1.42s3.55/1.42s3.15/2.38s2.65/2.57s2.41/3.02s1.70/3.02s
AOVRPB—/20.84m1.43/20.84m2.55/1.52s2.50/1.52s2.01/2.47s1.70/2.65s1.57/3.14s1.16/3.16s
AOVRPL—/20.84m1.89/20.84m3.43/1.48s3.38/1.49s2.96/2.43s2.41/2.63s2.29/3.09s1.77/3.11s
AVRPBL—/20.84m2.60/20.84m4.29/1.44s4.24/1.43s3.60/2.39s3.20/2.58s3.01/3.05s2.19/3.04s
AVRPTW—/20.82m1.09/20.82m3.42/1.46s3.51/1.47s2.68/2.42s2.49/2.61s2.41/3.08s1.85/3.09s
AOVRPBL—/20.84m1.46/20.84m2.56/1.52s2.51/1.52s2.01/2.46s1.69/2.65s1.63/3.13s1.16/3.14s
AOVRPTW—/20.84m0.62/20.84m1.40/1.64s1.45/1.66s0.91/2.59s0.76/2.79s0.73/3.33s0.43/3.34s
AVRPBTW—/20.84m1.00/20.84m3.32/1.49s3.33/1.49s2.58/2.44s2.33/2.63s2.29/3.11s1.80/3.12s
AVRPLTW—/20.84m1.09/20.84m3.57/1.49s3.70/1.50s2.86/2.45s2.71/2.64s2.61/3.12s2.08/3.13s
AOVRPBTW—/20.84m0.74/20.84m1.28/1.70s1.31/1.70s0.97/2.66s0.72/2.83s0.67/3.38s0.44/3.43s
AOVRPLTW—/20.84m0.61/20.84m1.43/1.65s1.51/1.65s0.96/2.62s0.80/2.80s0.76/3.34s0.44/3.35s
AVRPBLTW—/20.84m1.03/20.84m3.37/1.53s3.47/1.54s2.71/2.49s2.46/2.68s2.40/3.17s1.92/3.19s
AOVRPBLTW—/20.82m0.70/20.82m1.25/1.69s1.30/1.69s0.89/2.63s0.69/2.83s0.66/3.40s0.44/3.39s

Together, these results show that ARC's benefits extend beyond ATSP to a multi-task setting covering 16 asymmetric VRP variants. They support the broader applicability of assignment structure: adapting the assignment marginals to customer and depot roles preserves its value for neural representations and construction guidance.

W2: The presentation is also quite dense in places, especially in sections 2-3. Relying less on technical jargon and introducing the notation more thoroughly would improve the text substantially.

We apologize for the unclear presentation and thank the reviewer for this helpful feedback. We have provided more detailed explanations in our response to W1 from reviewer mALs. We will incorporate these clarifications into Sections 2 and 3. We will also reduce technical jargon and explain each symbol when it first appears to make the presentation easier to follow.

Thank you for the response, the presentation improvements and the additional experiment.

Could you add the two new tables to the manuscript? Preferably alongside a section detailing the experimental evaluation more carefully.

I would agree that the new results show the broader usefulness of ARC. Hence, if they are added to the manuscript and no additional concerns surface from any reviewer, I will raise my score from 2 to 3.

Reviewer_tXuAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents ARC, a neural framework for the asymmetric traveling salesman problem that explicitly models competition among nodes for incoming and outgoing connections. ARC uses a Sinkhorn-based assignment decomposition to derive node potentials and adjusted edge costs, providing structural inputs while preserving the relative costs of complete tours. During tour construction, Frontier Sinkhorn Pressure (FSP) approximately tracks changes in the remaining assignment requirements and uses this information to guide the neural decoder without repeatedly solving the full residual assignment problem. The policy is trained through reinforcement learning, while FSP can also improve existing policies without retraining.

Critical strengths
  1. ARC connects the one-incoming/one-outgoing constraints of ATSP to both representation learning and sequential decisions. The assignment potentials, adjusted costs, and residual guidance form a coherent method.
  2. The performance is promising. Training on 100-node instances transfers well to 2,000 nodes, where ARC-I reduces the gap in a large scale
Critical weaknesses
  1. ARC builds on RADAR and established assignment/Sinkhorn machinery. Its originality rests mainly on the particular input representation and FSP update, rather than a new optimization formulation or learning principle. Therefore, I think the conceptual advance is relatively narrow.
  2. The recursive update contributes only a small additional gain. Most of the guidance benefit is already obtained without recursion, which weakens the case for the paper’s most distinctive component.
Questions for authors
  1. How does ARC compare with assignment-based methods such as Trace-Guided Cost Augmentation, and what additional benefit does coupling assignment structure with a learned policy provide?
  2. How robust is ARC on instances where the assignment relaxation is much cheaper than any valid tour, and can FSP’s assignment-based guidance hurt solution quality in such cases?
6 comments

Thank you for your careful review. Below, we clarify ARC's contribution and FSP's role, and provide additional comparisons and robustness results. Revisions to the main text are highlighted in different colors.

W1: ARC builds on RADAR and established assignment/Sinkhorn machinery. Its originality rests mainly on the particular input representation and FSP update, rather than a new optimization formulation or learning principle. Therefore, I think the conceptual advance is relatively narrow.

We thank the reviewer for this thoughtful assessment. ARC indeed builds on RADAR and established assignment/Sinkhorn methods. We acknowledge that our presentation did not clearly convey its conceptual contribution. Our motivation comes from a largely overlooked issue in neural ATSP: problem constraints encode important dependencies between nodes, yet standard cost inputs do not make these dependencies explicit. Providing these dependencies directly gives the network structural knowledge for constructing a complete tour. To our knowledge, ARC is the first neural ATSP framework to use assignment structure to connect abstract problem constraints with concrete representations and dynamic tour construction. It makes complex node dependencies directly accessible to the network through simple representations, addressing an important gap.

Established neural ATSP methods such as RADAR [1] and MatNet [2] also build on existing mechanisms and introduce representations tailored to the problem. Their contributions show how a new representation can enable valuable capabilities within an established learning framework. ARC develops this direction by connecting problem constraints to both what the network receives and how it makes sequential decisions.

Beyond the specific input representation and FSP update, ARC contributes a systematic analysis of what structural knowledge neural solvers should receive, why it is useful, and why it changes during construction. First, the probes in Section 2.2 show that assignment features make useful connection preferences easier to identify than raw costs or simple cost statistics. They help identify connections belonging to high-quality tours before construction even begins. This suggests that constraint information can provide useful knowledge about subsequent decisions, motivating our explicit assignment inputs. Second, we analyze how selecting an edge changes the remaining connection requirements, even when the original costs stay fixed. This explains why the dependencies between nodes need to be updated as the partial tour grows and motivates FSP as an efficient way to maintain this information. Our representation and update mechanism thus follow naturally from these findings and form a unified framework.

Together, our analysis and experiments highlight a limitation of leaving these dependencies for the network to infer from costs alone. They motivate closer integration of problem constraints with neural solvers. Although ARC uses classical optimization tools and does not introduce a new learning principle, it identifies structural knowledge the network can use, explains why that knowledge changes during construction, and provides a unified way to incorporate it. We believe this constitutes a meaningful conceptual contribution to neural ATSP solving and offers researchers a concrete direction for further method design.

[1] RADAR: Learning to Route with Asymmetry-aware Distance Representations. Hang Yi, Ziwei Huang, Yining Ma, and Zhiguang Cao. ICLR, 2026.

[2] Matrix Encoding Networks for Neural Combinatorial Optimization. Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. NeurIPS, 2021.

W2: The recursive update contributes only a small additional gain. Most of the guidance benefit is already obtained without recursion, which weakens the case for the paper’s most distinctive component.

We thank the reviewer for this observation. Our presentation of the experiments may give the impression that recursive updates offer no practical benefit. We would like to clarify their role through three complementary findings from the appendix.

1. Recursive updates correct the growing mismatch between initial guidance and the remaining problem. As construction proceeds, the initial assignment information becomes less aligned with the remaining connection requirements. At 90% construction progress, FSP reduces centered destination-pressure error (MAE) by approximately 65% on ATSP500 and 70% on ATSP1000 compared with keeping the initial pressure fixed (Appendix D.3). The stage-window experiment further shows that applying guidance in the final third produces approximately twice the cost reduction of applying it in the middle third, at both sizes (Table 19). These findings explain why recursive maintenance is useful and necessary for keeping guidance aligned with changing requirements: it corrects the growing mismatch at the stage when guidance is especially valuable.

2. FSP delivers consistent improvements across independent training runs and multiple backbones. Table 18(c) evaluates three independently trained ARC-Base policies on 1,000 instances per size at ATSP500 and ATSP1000. Across these independent training runs and both problem sizes, FSP consistently reduces cost compared with static guidance. All six improvements are statistically significant at the 95% confidence level. FSP also improves over Static on frozen RADAR at both sizes (Table 7 and Table 18(a)). Thus, the gains recur across independently trained policies, large test sets, and multiple backbones, supporting a consistent benefit from recursive updates in these experiments.

3. FSP reduces the decoding budget needed to obtain better solutions. Table 11 compares ARC-I (recursive updates) with ARC-Static (no recursive updates) on 200 ATSP1000 instances. They share the same trained weights.

MethodStartsMean-cost gap (%)Latency (s/instance)
ARC-Static1,0001.2901.4886
ARC-I7681.2741.4501

The table shows that FSP substantially reduces the required decoding budget, obtaining better solutions with fewer starts and lower measured latency.

Taken together, we agree with the reviewer that most of the benefit of guidance can be obtained without recursion. We do not expect a lightweight recursive update to fully capture complex dependencies between nodes. Its purpose is to track changing connection requirements through an approximation that balances solution quality and computational cost. This reduces the mismatch between assignment guidance and what the model needs at each construction step. The improvements across multiple backbones further support its applicability. We will revise Sections 1–3 to present FSP more clearly as an efficient way to maintain and further improve assignment guidance, rather than as the source of most of the performance gain.

Q1: How does ARC compare with assignment-based methods such as Trace-Guided Cost Augmentation, and what additional benefit does coupling assignment structure with a learned policy provide?

We thank the reviewer for suggesting this comparison. TGCA [3] is a non-learning optimization method. It augments an assignment formulation with a trace penalty to discourage subtours, then recovers a complete tour when needed. ARC uses assignment structure to guide a policy trained to minimize the original tour cost.

Related learning-based approaches, including Goh et al. [4] and UTSP [5], also use assignment constraints, but their designs and experiments target Euclidean TSP. Their coordinate inputs or symmetric processing make direct extension to general asymmetric problems nontrivial. To our knowledge, ARC is the first neural ATSP framework to explicitly combine cost-derived assignment features with learned representations and dynamically updated construction guidance.

The following table compares our additional TGCA results with our method. Gaps are relative to LKH, and times are in minutes. ARC-Base gaps are from Table 2.

SizeTGCA gap (%)ARC-Base gap (%)TGCA time (min)ARC-Base time (min)
ATSP1000.35800.550.2610.037
ATSP2000.20930.530.8560.154
ATSP5000.09991.047.0261.487
ATSP10000.04202.3843.25111.908

With the larger time budgets shown above, TGCA achieves substantially better tour quality than ARC-Base. A key advantage of neural combinatorial optimization, however, is its ability to rapidly produce reasonable solutions for applications requiring fast responses. We therefore also evaluate TGCA using ARC-Base's measured runtime as its target budget:

SizeARC-Base budget (min)TGCA time (min)TGCA gap (%)ARC-Base gap (%)TGCA feasible tours
ATSP1000.0367460.0367463.7170†0.5467999/1000
ATSP2000.1541500.1541522.41690.52961000/1000
ATSP5001.4867821.4867871.26901.03761000/1000
ATSP100011.90829311.9096120.63132.37501000/1000

† At ATSP100, TGCA's gap covers only its 999 feasible tours; ARC-Base's gap covers all 1,000 instances.

Under these matched budgets, ARC-Base achieves lower gaps at ATSP100/200/500, while TGCA remains stronger at ATSP1000. These results demonstrate the value of learned construction under limited runtime and the potential of assignment structure. At the same time, while TGCA performs strongly on TSP, its single-tour formulation requires changes to handle multiple routes and additional VRP constraints. Our learning-based framework can be flexibly extended to VRP and related routing tasks. We will detail this extension in our response to Reviewer yTKz's W1 and Q1.

What the combination adds. Assignment structure and the learned policy offer three complementary benefits:

  1. Structural knowledge for tour construction. Assignment features expose competition among nodes but do not impose a single tour. The policy combines this information with the partial path and learns its decisions by minimizing the original tour cost. Our probes and input ablations support the value of these inputs (Section 2.2 and Table 5).

  2. Less reliance on many starts. In the single-instance ATSP1000 evaluation, ARC-Base with 16 starts achieves lower mean cost than RADAR with 1,000 starts, with 31.6% lower measured latency (Appendix C.1). Structured inputs therefore help the policy use its decoding budget more effectively.

  3. Guidance that transfers without retraining. FSP improves trained MatNet, ICAM, RADAR, and ARC-Base models without changing their weights (Figure 4), providing a reusable way to enhance existing policies.

Combining traditional optimization with learning thus supports fast construction with competitive solution quality and provides a flexible framework for extension to other routing tasks.

[3] Solving the Asymmetric Traveling Salesman Problem via Trace-Guided Cost Augmentation. Zhen Zhang, Javen Qinfeng Shi, and Wee Sun Lee. NeurIPS, 2025.

[4] Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem. Yong Liang Goh, Wee Sun Lee, Xavier Bresson, Thomas Laurent, and Nicholas Lim. arXiv:2203.00903, 2022.

[5] Unsupervised Learning for Solving the Travelling Salesman Problem. Yimeng Min, Yiwei Bai, and Carla P. Gomes. NeurIPS, 2023.

Reviewer_mALsOpenReview ↗
Rating
3(+2)
Confidence
2
Informativeness
2
Presentation
3(+2)
Soundness
3
Read review
Paper summary

The paper proposes ARC, a neural solver for the Asymmetric Traveling Salesman Problem. The key idea is to incorporate soft assignment information (computed via Sinkhorn iterations on the cost matrix between source and destination nodes) into the neural representation and tour construction process. The method proposes to use Sinkhorn information to derive node potentials and adjusted edge costs as input features to the network and also update as the tour is constructed. Experiments are performed on synthetic ATSP instances up to 2000 nodes and real-world road datasets, where the method has benefits in both speed and accuracy over existing neural solvers.

Critical strengths
  1. The experimental results seem promising showing improvements in the gap to optimal performance as well as inference, highlighting the importance of assignment information in better neural ATSP solvers.
Critical weaknesses
  1. The clarity of the paper is substantially limited, which is the primary reason for my low score. While I am familiar with various ideas and the problem at a high level, I found it extremely difficult to parse the first 3 sections of the paper to understand what the method is actually doing. Specifically, Section 2.1 states a bunch of definitions without motivating why they are necessary (why is assignment helpful? why does Sinkhorn help?). The next section starts introducing probes (which I gather as being AI-written although the AI statement states the authors led manuscript writing) and the setup is not at all clear to me. For example, what is accuracy of reference edge in Figure 1a and what is Hit@1 in Figure 1b? Without defining the experiment, it is not possible to extract meaningful conclusions. Similarly, I am unable to understand Figure 2: what is "guidance" here and how is this showing that assignment is useful? Further, regarding clarity, the next section talks about Frontier Sinkhorn Pressure (FSP) without defining it. As far as I am aware, this is not a standard definition and even after reading multiple times, I do not understand how this is used to iteratively obtain better estimates as tour is being constructed. The term Gauge is also used without defining it and I am unsure why it is needed. The paper would benefit from better explanation of several design choices such as SVD-based design choices or why the specific form of Equation 3.
  2. From the writing, I gather that RADAR also uses Sinkhorn-derived information but modifies attention maps instead. Why does this method perform better than RADAR if both use fundamentally the same information?
Questions for authors

See weaknesses above.

7 comments

Thank you for your careful review and detailed comments on the clarity and methodology of our paper. Your feedback has helped us identify where the motivation, definitions, and design choices need clearer explanations. Below, we address your concerns about the assignment formulation, probe experiments, FSP, Gauge, and the relationship to RADAR. We have revised the corresponding parts of the manuscript to make the presentation easier to follow, with changes to the main text highlighted in different colors. We hope these responses and revisions clarify both how ARC works and why its components are useful.

W1: The clarity of the paper is substantially limited, which is the primary reason for my low score. While I am familiar with various ideas and the problem at a high level, I found it extremely difficult to parse the first 3 sections of the paper to understand what the method is actually doing.

We apologize for the unclear presentation. In condensing the main text, we left several essential explanations in the appendix. These explanations should have appeared before the definitions and figures. We also introduced several concepts too abstractly, without first explaining their meaning and purpose.

We have clarified the motivation and will reorganize the first three sections to make the reasoning easier to follow. Below, we address each concern in turn.

1. Specifically, Section 2.1 states a bunch of definitions without motivating why they are necessary (why is assignment helpful? why does Sinkhorn help?).

Thank you for pointing out that our motivation was not clearly explained. We omitted several explanations needed to connect the ideas, and we will make these connections explicit in the revision.

Many neural routing methods learn representations from basic inputs, such as node coordinates or raw cost matrices. However, known problem constraints also imply dependencies between nodes that are not explicit in these basic inputs. The network must therefore learn these complex dependencies on its own and identify which ones are relevant to tour construction. To address this, we introduce the assignment problem to provide the network with this structural information and reduce its learning burden.

The assignment problem captures the one-to-one matching relationships between nodes. Its solution provides an initial reference for choosing which nodes to connect. This assignment structure matters because several source nodes may compete for the same destination, but only one can be matched to it. Choosing a cheap edge for one source can leave another source with a much more expensive alternative. The total cost can therefore increase. These joint effects are not explicit in individual edge costs. The assignment problem evaluates these choices together, so its solution accounts for both edge costs and competition among nodes.

The close relationship between assignment and ATSP is supported by theory and our experiments. For independent uniform random costs, the gap between the optimal assignment and ATSP costs vanishes as the instance size grows [1] (Appendix A.1). In our experiments, we also observe that assignment solutions become more similar to ATSP solutions as the instance size increases. From N=100N=100 to N=1000N=1000, the mean relative cost gap decreases from 0.3673% to 0.0310%, while directed-edge overlap increases from 79.780% to 84.961%.

NNMean relative cost gapDirected-edge overlap
1000.3673%79.780%
2000.1739%82.760%
5000.0747%84.190%
10000.0310%84.961%

The small cost gaps and substantial edge overlaps support assignment as a useful structural starting point for tour construction. The increasing similarity at larger sizes further motivates using assignment information in both the network's representation and its construction decisions.

Obtaining this reference through repeated exact assignment solves can be costly, particularly for large instances. We therefore use a continuous, entropy-regularized version of the assignment problem. Sinkhorn provides an efficient iterative method for solving this problem. The resulting soft matching matrix expresses connection preferences that account for both costs and competition. We use this information to enrich the input representation and support the network during tour construction.

We will add these explanations to Sections 1 and 2.1 to make the motivation and the progression of ideas clearer.

[1] The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems. Alan Frieze and Gregory B. Sorkin. SIAM Journal on Computing, 2007.

2. The next section starts introducing probes (which I gather as being AI-written although the AI statement states the authors led manuscript writing) and the setup is not at all clear to me. For example, what is accuracy of reference edge in Figure 1a and what is Hit@1 in Figure 1b? Without defining the experiment, it is not possible to extract meaningful conclusions.

We thank the reviewer for pointing out the missing details of the experimental setup. We also clarify that the authors led the writing, with AI assistance for language editing. As noted above, we compressed the presentation too much to meet the space limit and placed many details in the appendix. The essential experimental setup should have appeared in the main text.

Inspired by Probing Neural Combinatorial Optimization Models [2], these experiments ask whether assignment features capture dependencies between nodes that individual raw edge costs do not convey. We also test whether these features already contain information useful for tour construction before a routing policy is trained.

Figure 1a: identifying the optimal edge among candidates with similar costs. Each sample contains two edges: one from a reference solution generated by LKH, and one outside that solution with a similar cost. In this experiment, we use the edge in the LKH reference solution as the label for the "optimal edge."

We compare three feature sets: the original edge cost alone, the cost plus row/column statistics, and the cost plus the assignment features introduced in Section 2.1. The row/column statistics include the mean and minimum outgoing costs of the source node and incoming costs of the destination node. This baseline tests how much information simple local cost summaries provide for distinguishing the two edges.

For each feature set, we concatenate the feature vectors of the two edges and train a linear classifier to identify the optimal edge. Accuracy is the fraction of pairs in which the optimal edge is correctly identified, with half credit for tied predictions. The three feature sets achieve 50.00%, 87.25%, and 90.52%, respectively.

Figure 1b: ranking all candidate destinations. For each source node, we rank all N−1N-1 other nodes as candidate destinations. We compare the original cost, a mean-centered cost, and a cost derived from the soft matching solution. If QijQ_{ij} is the soft matching weight for the edge from node ii to node jj, the last cost is

Cij′=−τlog⁡Qij,C_{ij}^{\prime}=-\tau\log Q_{ij},

where τ>0\tau>0 is the temperature parameter. Lower costs therefore correspond to higher soft matching weights.

No classifier is trained in this experiment. We directly rank the candidate destinations by increasing cost under each of the three representations. Hit@1 is the fraction of source nodes whose top-ranked destination is their next node in the LKH reference solution.

These results show that information relevant to tour construction is easier to extract from assignment features than from raw edge costs or local cost statistics. This supports the motivation in Section 2.1: explicitly providing assignment information gives the network access to node dependencies relevant to construction decisions before it learns a routing policy.

3. Similarly, I am unable to understand Figure 2: what is "guidance" here and how is this showing that assignment is useful?

We thank the reviewer for pointing out this ambiguity. We did not clearly explain what we meant by "guidance." In Figure 2, "guidance" refers to the soft matching weights, which express connection preferences between nodes and provide a reference for edge selection.

The main point of this discussion is that the remaining assignment problem changes as the tour is constructed, so assignment information needs to be updated to reflect the current state. Here, "state" refers to the partial tour already constructed and the nodes still to be visited. Before any edge is selected, the soft matching solution describes connection preferences for the full instance. As the tour is constructed, each selected edge fixes part of the solution and changes the remaining matching requirements. This changes competition between nodes. The corresponding soft matching weights can therefore change even if the remaining edge costs stay the same.

Figure 2 provides a simple illustration of this process, rather than an evaluation of whether assignment information is useful. The preceding analysis and Figure 1 provide evidence that assignment information is relevant to tour construction. Figure 2 explains why this information needs to be updated as construction proceeds.

We will revise the accompanying text and the Figure 2 caption to make the purpose of the figure clear.

[2] Probing Neural Combinatorial Optimization Models. Zhiqin Zhang, Yining Ma, Zhiguang Cao, and Hoong Chuin Lau. NeurIPS, 2025.

4. Further, regarding clarity, the next section talks about Frontier Sinkhorn Pressure (FSP) without defining it. As far as I am aware, this is not a standard definition and even after reading multiple times, I do not understand how this is used to iteratively obtain better estimates as tour is being constructed.

We thank the reviewer for pointing out the missing definition. Section 2.2 explains why assignment information needs to be updated during tour construction. However, although Sinkhorn is an efficient iterative solver, rerunning it on the entire remaining matrix after every decision still incurs substantial cumulative computational cost. We therefore propose an iterative method for approximating the soft matching solution of the remaining problem. It first uses Sinkhorn to obtain an initial soft matching solution, then updates destination corrections (pressure) after each decision using the cached row of the path endpoint (frontier) from before that decision. The initial soft matching solution and the updated corrections are then used together to approximate the soft matching solution of the remaining problem. We call this method Frontier Sinkhorn Pressure (FSP).

FSP stores a fixed matrix derived from the initial soft matching solution, together with one correction value for each destination. It does not maintain a fully updated soft matching matrix for the remaining problem. Instead, it computes and caches only the row needed for the current decision. The procedure is as follows:

  1. Before selecting the next node, FSP combines the current endpoint's row in the fixed matrix with the destination corrections. It then normalizes and caches this row of soft matching weights. The normalization covers destinations that still need an incoming edge: the unvisited nodes and the start node reserved for closing the tour.

  2. After selecting the next node, one edge has been fixed and the state changes. The previous endpoint's source row and the selected node's destination column are excluded from subsequent assignment. FSP uses the cached row to estimate how much weight each remaining destination loses when that source is removed. It then updates the correction value for every remaining destination. This updates the destination vector without rerunning Sinkhorn on the entire remaining matrix.

  3. At the next step, the selected node becomes the new endpoint. FSP computes and normalizes its row using the fixed matrix and the updated destination corrections. This process repeats as the tour is constructed.

Each step therefore queries one row and updates the destination corrections. The fixed matrix and these corrections together implicitly represent an approximately updated soft matching solution.

As in Figure 2, these soft matching weights express connection preferences between nodes. During neural decoding, we convert these weights into structural scores and incorporate them into the neural policy to guide tour construction.

By "better estimates," we mean more accurate estimates of the soft matching weights for the current remaining problem. Specifically, the selected edges fix part of the solution, satisfying the corresponding outgoing and incoming requirements. Rerunning Sinkhorn on the remaining matching problem gives a reference soft matching solution for the current state. Compared with retaining the initial soft matching information, FSP's updated weights more closely match the corresponding weights in this reference solution. Each update accounts for the matching requirements changed by the latest selected edge.

We will reorganize the explanation in Section 3.2 and improve the wording to make this process clear.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.