COMPASS: Ordered Clustered Routing at 100K Scale
Ido Greenberg, Hugo Linsenmaier, Piotr Sielski, Shie Mannor, Alex Fender, Gal Chechik, Eli Meirom
cs.LG
Quick verdict
COMPASS (search+RL, endpoint-DAG) claims SOTA OCTSP routing to 100K nodes and new optimality certificates; convincing, but gaps use self-defined BKS.
Summary
The paper addresses OCTSP — nodes grouped into ordered clusters that must be visited in sequence — over general, possibly asymmetric distance matrices. COMPASS represents the whole cluster chain as a layered DAG over candidate entry/exit endpoints: intra-cluster sub-TSP costs come from an RL-accelerated genetic solver (EARLI warm-starting cuOpt), bridge costs from the raw distance matrix, and a DP shortest path picks endpoints globally, removing the quality ceiling of local decompositions. With exhaustive endpoints plus an exact sub-solver, optimality is certified in time exponential in cluster size, not instance size; on Ahmed's 23 small instances it certifies all 23 optima, 9 never certified before. On new released benchmarks — synthetic polyomino 10K/100K nodes, Olist São Paulo 11K, and one 28,479-node instance with asymmetric driving times — COMPASS attains the best cost everywhere, e.g., 0.00% gap in 16.0 min on SP-11K versus LKH-3's 3.11% in 67.8 min; at 100K nodes LKH-3, CLKH and NeuroLKH do not finish. Limitations: gaps are measured against a best-known solution that COMPASS itself defines; headline runs use 16 H100s versus single-threaded CPU LKH baselines and a single-GPU Slider; statistics rest on 4-16 instances (a single instance at 28.5K); and no ablations isolate the endpoint-selection heuristics or the RL component.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 4
● low 1
4 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Encoding the full cluster chain as a layered DAG over candidate endpoints and solving shortest path by DP removes the quality ceiling that limits per-cluster and sliding-window decompositions (Prop. 1).
- With exhaustive candidate endpoints and an exact sub-solver, OCTSP is solved exactly in O(m·n⁴·2ⁿ) — exponential in cluster size, not instance size (Cor. 2) — newly certifying 9 instances of Ahmed (2014).
- COMPASS achieves the best reported costs on all evaluated benchmarks, e.g., 0.00% gap in 16.0 min on São Paulo 11K versus LKH-3's 3.11% in 67.8 min (Table 2).
- The single 28,479-node São Paulo instance over asymmetric driving times is, to the authors' knowledge, the largest asymmetric distance-matrix routing solution reported, roughly 9× the prior 3.2K-node ATSP mark.
- COMPASS solutions keep improving with runtime and compute, from 1 to 16 H100 GPUs, with no quality ceiling (Fig. 5).
Strengths
Conditional optimality guarantee with real certifications
Prop. 1 + Corollary 2 give an exact O(m·n⁴·2ⁿ) regime; Table 3 shows COMPASS certifying 23/23 Ahmed instances in 3.3 s versus LSA's 14/23, adding 9 first-ever optimality certificates.
Above-average baseline diligence
Appendix C.3: the Hybrid GA reimplementation reproduces the 2014 paper's worked example; CTSP-d MILP was ported to HiGHS and verified against the original d=0 results before being declared infeasible (290 GB RAM); LKH-3 is fed a feasible initial tour to stabilize M-reduction.
Clean motivation of the modeling gap
New released benchmarks with leakage controls
Weaknesses
Self-referential BKS
Hardware-asymmetric headline comparison
Thin instance counts and informal significance
No ablations of key components
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper targets OCTSP: N nodes partitioned into m ordered clusters, each traversed as a Hamiltonian path before the next cluster begins, with costs from a general, possibly asymmetric, distance matrix (Sec. 3). Central claims: (1) local decompositions (Solve-first, Connect-first, Pairwise Slider) impose a quality ceiling because they miss cross-cluster coupling, which COMPASS removes by encoding the whole chain as a layered DAG over candidate entry/exit endpoints selected via DP shortest path (Secs. 4-5, Prop. 1); (2) with exhaustive endpoints and an exact sub-solver, OCTSP falls in O(m·n⁴·2ⁿ) — exponential in cluster size rather than instance size (Cor. 2); (3) COMPASS is SOTA on new 10K/100K synthetic and 11K/28.5K São Paulo benchmarks (Table 2); (4) the 28,479-node asymmetric instance is, per the authors, the largest asymmetric-matrix routing solution reported, about 9× the prior 3.2K-node ATSP mark (Secs. 1-2).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the Ordered Clustered TSP (OCTSP)?
OCTSP is a routing problem where nodes are grouped into clusters that must all be visited in a prescribed order — every node of cluster i before any node of cluster i+1. Each cluster is traversed by a Hamiltonian path, and consecutive clusters are joined by 'bridge' edges. It models tiered last-mile delivery, priority service, or emergency triage, and can be defined over arbitrary asymmetric distance matrices such as road driving times, not just coordinates.
How does the COMPASS algorithm work?
COMPASS treats each cluster's entry and exit nodes as decision variables. For each cluster it keeps K candidate endpoint pairs, estimates the best path cost for each pair with an RL-accelerated sub-TSP solver (EARLI warm-starting a cuOpt genetic algorithm), adds bridge costs taken directly from the distance matrix, and finds the globally best endpoint combination via a dynamic-programming shortest path over the resulting layered graph. Winning sub-problems then get extra optimization time. This global coupling removes the quality ceiling of methods that optimize clusters locally.
Is COMPASS an exact solver?
Only in a restricted regime: if every possible endpoint pair is a candidate and each sub-TSP is solved exactly (e.g., Held–Karp), COMPASS is provably optimal in time exponential in the cluster size rather than the instance size — practical only for small clusters. This was demonstrated on 23 instances of 14–51 nodes, where it certified 9 previously-uncertified optima in seconds. At 10K–100K nodes it runs as a heuristic that improves with compute, with no independent optimality bound reported.
What data and code are available for this paper's benchmarks?
The authors state they release two benchmark suites with generators: synthetic non-convex 'polyomino' instances with 10K and 100K Euclidean nodes, and real e-commerce instances from the Olist São Paulo dataset (11K nodes per instance, plus one 28,479-node instance with asymmetric OSRM driving times); a Rio de Janeiro set is used only for training, avoiding test leakage. The paper does not explicitly state that the COMPASS solver code itself is released.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures (1, 2, 4-9) are known only via captions; the Pareto-front curves and error bars of Fig. 5 could not be verified numerically from the extracted text.
- RL/GNN training details (model size, PPO hyperparameters) are not in the extracted text, limiting assessment of the learning component.
- Only benchmarks and generators are explicitly stated as released; solver-code release scope is unclear, which the review reflects rather than assumes.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.