Calibrating Learned Tour–Packing Compatibility in the Traveling Thief Problem

Many real optimization problems are really two problems that pull on each other. In the Traveling Thief Problem, a thief chooses a route through cities (a traveling-salesperson problem) and which items to steal along the way (a knapsack problem). Heavy items slow the thief down, so the best set of items depends on the route, and the best route depends on the items. The strongest solvers for the two-objective version handle this coupling by running an exact dynamic program that computes the best packing plans for every candidate route. That is accurate but very expensive: one study reports about 170,000 CPU-hours. A natural way to cut the cost is to learn, once, a scoring function between routes and packing plans. Then most candidate routes can be judged, and given a starting packing, without running the dynamic program.

The natural model for this is a dual encoder, the CLIP-style design in which routes and packings each get their own neural encoder and compatibility is the dot product of the two embeddings. Dual encoders carry a known flaw from multimodal learning: the modality gap, where embeddings of the two input types sit in separate regions of the shared space. This note argues that the gap is harmless for one use and harmful for another, and that the bi-level search loop needs both. Ranking packings for one fixed route is unaffected by the gap. Comparing routes against each other through their best packing score is distorted by it. We propose to measure this effect, to fix it with cross-route calibration, and to test whether the fix turns a learned surrogate into a solver that is cheaper than nested dynamic programming and nearly as good.

Core Claim

Let $z_t$ be the embedding of route $t$ and $z_p$ the embedding of packing plan $p$, with compatibility $s(t,p) = \langle z_t, z_p\rangle$. Write each packing embedding as a centered part plus the packing-side mean offset $g$, so $z_p = \tilde z_p + g$. Then

$$ s(t,p) = \langle z_t, \tilde z_p\rangle + \langle z_t, g\rangle . $$

The second term depends only on the route. A contrastive loss that applies a softmax over packings for each route is exactly blind to it. That is the natural training direction here: "given this route, which packing goes with it?" The symmetric CLIP-style variant also normalizes over routes for each packing, but it sees this term only relative to the other routes in the batch, so it constrains it only weakly. Vision-language studies report that CLIP-trained spaces still keep a large gap; we will measure how much route-dependent offset survives in our setting.

Ranking packings for a fixed route ignores this term. Screening routes by $\max_p s(t,p)$ does not: it adds a route-specific bias with no relation to route quality. Our core claim follows. Dual encoders for interdependent combinatorial problems should be judged and trained on cross-query calibration, not on per-query retrieval. The modality gap is the geometric form that the missing calibration takes. Closing the gap, or replacing the contrastive objective with one that ties scores to true objective values across routes, should improve route screening and leave packing retrieval roughly unchanged.

This sharpens an observation already in the file. Closing the Modality Gap Aligns Group-Wise Semantics reports that rank-based retrieval barely notices the gap, while distance-based group tasks break when a gap exists. It also reports a roughly 60-degree equilibrium gap, with MSCOCO gap distance falling from 0.47 to 0.03 under its loss. We identify which operation inside a combinatorial search loop is the distance-based one.

The claim also bears on an apparent contradiction in the file. Mind the Gap finds that keeping a non-zero gap can help zero-shot classification. Classification is a per-query ranking task. Our account predicts that keeping the gap is fine for such tasks and harmful only when scores are compared across queries. That prediction is testable.

Research Program

Role of each line of prior work. The motivation comes from the Traveling Thief literature.

The method comes from the modality-gap literature.

Closest neural combinatorial work, and how we differ. - ConRep4CO aligns a graph instance with its satisfiability (SAT) reduction using InfoNCE, the standard contrastive loss. Its positive pairs are two equivalent descriptions of one problem. Ours are two halves of a solution whose compatibility is graded, and the paper never measures its gap. - Neural Multi-Objective Combinatorial Optimization via Graph-Image Multimodal Fusion fuses graph and image views of a single instance through small exchange bottlenecks. It does not represent interacting decisions or study the geometry of the fused space. - MuFasa and L2Sep model multi-part decisions with a joint aggregator network. That design is accurate but must score every pair jointly. It cannot score a whole packing library against many routes with one matrix product, and that cheap all-pairs scoring is the reason to use a dual encoder.

What we build. 1. A route encoder: a graph network over the tour, with position-in-tour features, because an item's cost depends on how late it is picked up. 2. A packing encoder: a set encoder over selected items, carrying each item's city, weight and profit. 3. Training pairs from small instances of the eil51, eil76 and eil101 families. Routes are sampled by perturbing Chained Lin-Kernighan tours, and packings are taken from the exact dynamic-programming fronts plus perturbed variants. Every pair is labeled with its exact scalarized objective under randomly drawn objective weights. Evaluating one pair costs time linear in instance size. 4. Four training objectives: - route-to-packing InfoNCE; - symmetric InfoNCE; - InfoNCE plus gap closure; - a calibrated objective that regresses $s(t,p)$ onto the true scalarized value across all routes and packings in a batch, which directly penalizes the route-only term.

How the model is used in search. Inside the bi-level evolutionary algorithm, a new route is first screened by $\max_p s(t,p)$ over a packing library. Only routes in the top fraction proceed to the exact dynamic program. Rejected routes still contribute their top retrieved packings, repaired with a (1+1) evolutionary algorithm, so the archive is not starved.

Diagnostics. We record four quantities for each model:

  • gap distance between the centroids of the route and packing embeddings;
  • linear separability of the two modalities; Mind the Gap reports 100% on CLIP;
  • the variance across routes of $\langle z_t, g\rangle$;
  • the correlation of that variance with screening error.

Baselines

Naive reference. The bi-level evolutionary algorithm with no learned screening: every route either receives the full dynamic program, or, in a cheap variant, receives greedy packing in the style of Iterated Greedy Packing. These bracket the trade-off between accuracy and cost that the learned model must beat.

Strongest existing method. The indicator-based evolutionary algorithm with nested exact dynamic programming from Evolutionary Computation plus Dynamic Programming for the Bi-Objective Travelling Thief Problem. The file records that it beat the earlier MA2B solver on most eil51/76/101-family instances under Welch's t-test, at about 170,000 CPU-hours. No reported hypervolume value for it was found on Lacuna, so we will rerun it ourselves.

Second strongest. BMBEA from On the Use of Quality Diversity Algorithms for The Traveling Thief Problem, which reports a higher average score on 16 of 18 instances.

Fair comparison. All methods run on the same instances, with the same wall-clock and CPU budget. The learned model's training and labeling cost is charged to it. Hyperparameters get equal tuning trials.

What counts as beating them. Statistically indistinguishable hypervolume at one tenth of the compute, or higher hypervolume at matched compute.

Ablations. The ablation that isolates our key ingredient trains the same dual encoder with route-to-packing InfoNCE versus the calibrated objective, holding architecture, data and screening threshold fixed.

Learned-model ceiling. A joint cross-encoder that reads route and packing together and regresses their value. This is the accuracy ceiling for learned scoring, with its extra cost reported.

Why not just…?

Why not just use the holistic memetic algorithm or ReinforceNS and skip learning altogether? For the single-objective problem this is a serious option. ReinforceNS outperformed the prior best on 38 of 60 instances within 600 seconds, and set 12 new best-known results on the GECCO 2023 competition instances. Our target is narrower: the bi-objective setting, where full packing fronts are needed and exact dynamic programming dominates the cost. As a secondary check, we will report whether screening routes inside a ReinforceNS-style loop helps under its 600-second budget, scored by its Relative Deviation Index. If it does not, we will say so.

Why not just train a single network that maps a route directly to its best achievable value? This is the main threat to the screening half of the method. Such a regressor never mixes modalities, so it has no gap. We include it as a baseline. If it matches the calibrated dual encoder at screening, then the dual encoder earns its place only through retrieval warm-starts. Those warm-starts are separately measured as dynamic-program calls saved per accepted route. A regressor cannot supply them, because it outputs a number, not a packing.

Why not just subtract each modality's mean embedding after training? Removing $g$ after training eliminates the route-only term in the equation above. If it closes most of the screening gap, it is the cheapest correct fix, and we will recommend it. We expect it to fall short of training-time calibration. Per-route offsets can also arise from directions other than the centroid, which the variance diagnostic will reveal.

Why not just use plain InfoNCE, as ConRep4CO does? Plain InfoNCE is the hypothesis under test. Our prediction is that it matches the calibrated model on per-route retrieval, scored by normalized discounted cumulative gain (NDCG) of packings, and is worse on cross-route screening. Finding both halves of this split would support the core claim. Finding no difference on screening would falsify it.

Proposed Experiments

Instances and splits. - Training: generated eil51, eil76 and eil101-family instances. - Held-out test: unseen item-density and capacity types from the same families. - Size transfer: the Polyakovskiy suite instances up to 280 cities.

Decisive check 1, cross-query versus per-query. Within-route packing NDCG should be similar across the four objectives. Cross-route screening quality should differ, measured two ways:

  • Spearman correlation between $\max_p s(t,p)$ and the true dynamic-program optimum across routes;
  • the fraction of true top-decile routes kept at a fixed screening rate.

Plain InfoNCE should screen worse. Its screening error should track the variance of $\langle z_t, g\rangle$. We repeat this across temperatures, because low temperature should enlarge the gap.

Decisive check 2, the classification contradiction. We deliberately inflate the gap by shifting embeddings, as Mind the Gap does. The prediction is that per-route retrieval stays flat while screening degrades as the gap grows. This would reconcile that paper's finding with ours.

Decisive check 3, collapse. For gap-closing training, track the effective rank of the embeddings and the variety of retrieved packings. This guards against the representation collapse that FindRec warns about.

End-to-end comparison. We report hypervolume, attainment of the Pareto front, and CPU-hours against the baselines above.

Overall test. The claim holds if calibrated or gap-closed screening reaches the dynamic-program baseline's hypervolume at a small fraction of its compute, while plain-InfoNCE screening at the same threshold falls measurably short.