acceptodds
Under review as a conference paper at ICLR 2027

Problem-Dual Augmentation and Training for Neural Combinatorial Optimization

Abstract

Much recent progress in neural combinatorial optimization comes from generating more varied candidate solutions for each instance. For Euclidean routing, instance augmentation—solving rotated and reflected copies of an instance—does this reliably, but job scheduling problems have no geometry to transform and lack a widely used counterpart that changes the model's input while preserving the objective exactly; MatNet's random machine embeddings, the closest mechanism, act like resampling. We show that classical problem duality provides a non-geometric one. An exact dual instance T(I) has feasible solutions in an objective-preserving bijection with those of I, so any solution's cost is read directly off T(I). The transformations are largely classical in operations research; what is new is their use as model-agnostic test-time augmentation for learned solvers, which we study on the asymmetric traveling salesman problem (ATSP) and five scheduling problems: permutation and flexible flow shop, job shop, flexible job shop, and single-machine scheduling with total weighted tardiness. The dual admits two uses. Problem-dual augmentation (PDA) solves I and T(I) with one trained model, typically at the same candidate budget as solving I alone. It needs no retraining and improved the forward-only solver in 30 of 32 problem–size settings with a static dual, tying in one; the gain comes neither from the dual being easier nor from drawing more samples, but from the two candidate sets being complementary. Problem-dual training (PDT) shares one model across both directions, and its effect is problem-dependent: it narrows the remaining ATSP gap by about a tenth, from 3.62% to 3.27%, yet on job shop scheduling it offsets part of augmentation's gain, and on flexible job shop the sign of its effect changes between training runs. Combined, the two improve the forward-only solver in 28–30 of 35 settings, depending on the training run. Neither use changes the network architecture or the learning algorithm, and we apply both to four published solvers trained by supervised, reinforcement, self-imitation and preference learning.

Primary area:
optimization
Keywords:
neural combinatorial optimization, scheduling, problem duality, instance augmentation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_FGusOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The manuscript is motivated by the primal and dual properties in combinatorial optimization problems. It first transforms the instances into equivalent problems, such as by transposing the distance matrix of the asymmetric TSP. The transformed instances are then input to either the training or inference phases. The proposed method is evaluated on asymmetric TSP and five scheduling variants. Results show that applying on inference is helpful, while training with such augmentation deteriorates the performance.

Critical strengths
  1. The idea of adopting the primal and dual properties in COP is interesting.
  2. The code is provided.
Critical weaknesses
  1. The presentation is very poor. It seems to be AI-generated, with so many details and unclear statements. It is difficult to follow despite careful reading.
  2. A similar idea has been considered in [1]. Careful positioning and differentiation against prior works will strengthen the manuscript.
  3. It is so straightforward to just use the equivalent transformation as inputs. It would be more interesting to rethink a more suitable use for the duality.
  4. Why does the use in training deteriorate the performance on scheduling? I expect a more in-depth understanding of it.
  5. More importantly, why do we need such a transformation for NCO? What special benefits and insights can it bring to the community?

[1] Generalization in deep RL for TSP problems via equivariance and local search.

Questions for authors

See above.

1 comment
AuthorsOpenReview ↗

Response to Reviewer FGus: why PDA matters and relation to prior work

Thank you for the careful review. Your questions, why training on the dual can hurt and what duality offers NCO, are the ones our new experiments were designed to answer. We summarize the answers first, then the changes to the paper.

What duality offers NCO. NCO has had two ways to improve a trained model at test time: geometric augmentation, which exists only for Euclidean routing, and search (active search, EAS, SGBS, COMPASS), which needs extra gradient steps or a model trained for it. The dual is a third way that needs neither. It brings two findings we did not expect:

  1. Varied candidates matter more than more candidates. On JSSP, K/2K/2 original + K/2K/2 dual candidates beat 2K2K original candidates (7.79% vs. 8.11%, Table 2). The dual is not just more input; it reaches solutions that more sampling of the same model does not.
  2. It improves models we did not train. On the checkpoint released by the MP-ASIL authors, PDA lowers the Taillard gap from 7.69% to 7.01% (pp = 0.0001) at 1.58 times the inference time, with no retraining. For scheduling, where no augmentation existed, this is a free gain for any released solver.

Training does not always hurt, and we now know when it does. PDT helps when the dual adds training signal and not when it splits it (general response, point 2; reply to 2xck):

  • With supervised labels (ATSP-GOAL), the dual of each training instance is one more exactly labeled example, so PDT doubles the labeled data at no labeling cost. The model improves in both training runs (4.67% → 4.20%, 4.74% → 4.43%), and PDAT beats or ties FWD+PDA.
  • With self-imitation (JSSP), the model learns from the best of its own samples. PDT splits those samples between two directions, so each direction learns from a weaker target, and the model gets worse (8.47% → 8.76%).
  • PFSP and FFSP sit in between: the model changes little, and PDAT ties FWD+PDA.

So the answer to "why does training hurt on scheduling" is that our scheduling backbones learn from their own samples, not that scheduling is special. We also tested tying the two directions more tightly, so that both imitate the best solution of either direction: the PDA gain almost vanishes (0.23 → 0.05 on PFSP), because PDA needs the two directions to differ. The better use of duality in training is therefore as extra labeled data, as in supervised learning; the better use at test time is PDA, which needs no training at all.

Relation to [1]. Ouyang et al. (2021) use the geometric symmetries of Euclidean TSP (rotation, reflection) for equivariant policies and local search. ATSP and scheduling have no such geometry. Our transformations are exact problem duals (time reversal, machine reversal, matrix transposition) that keep the objective value. The revision cites [1] and states this difference.

Soundness. Win counts are replaced by paired Wilcoxon tests with 95% confidence intervals on every problem (general response, point 1). Claims that are not significant are reported as ties, and conclusions that rest on one training run are marked as such.

Presentation. We take this seriously. We used AI assistance and disclose it, as ICLR requires; the experiments, analyses and claims are our own. The revised PDF, which we will upload in this discussion period, is built around these answers, with one table for each, and moves the per-problem details to the appendices. For any further revision, the manuscript will also be edited by a professional editing service.

Reviewer_2xckOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Recent work shows that generating varied candidate solutions can improve the quality of neural solvers. While instance augmentation is straightforward for Euclidean routing problems (by rotation or reflection), many other problems do not have a simple method for this.

This work represents an attempt to fill that gap by exploiting the dual nature of combinatorial problems. The work is well-motivated, but in the current version, the contribution is not clear and many questions remain.

Critical strengths
  • The idea of using dual problems in NCO is clear and straightforward, and the paper is well written and easy to follow. PDA does not require any retraining and can be applied to any existing NCO model that solves problems with a static dual.

  • This is a good attempt to augment instances of problems that do not have trivial augmentations (like rotation, translation and reflection in Euclidean routing problems). However, duality allows only one additional augmented instance per instance, which is probably not enough.

Critical weaknesses
  • The novelty is limited and the work is almost trivial, especially PDA. As the authors acknowledge, the duals themselves are classical and well known in the CO community. This paper only applies duality properties to neural solvers, which is useful but rather incremental and not enough for a venue like this.

  • The main contribution of this paper could be method for dual training (PDAT), but the results are not convincing. The method works well on average, but not consistently. In some settings PDAT is worse than PDA, for example on 6 of 8 JSSP sizes (Table I3). The main question is why this happens and what makes these problems or settings specific, but the explanation is incomplete. The authors offer a few hypotheses, but none of them is sufficient to draw a clear conclusion, for example why ATSP benefits from dual training, or why on FJSP dual training helped in one training run and hurt in another, as Table J6 shows.

Questions for authors

Q1: Several of your experiments rely on a single training run (ATSP, PFSP, JSSP), and two use a reduced training budget (ATSP, and JSSP), so strong conclusions may not be possible for them, especially since experiments with FJSP shows that different training runs can lead to very different results. Did you try more exhaustive trainings for all problems (with more runs and more training steps)?

Q2: The summed loss looks as a very naive approach, especially given the different training procedures used in this work (supervised learning, REINFORCE, self-imitation and preference optimization). To be honest, it is very surprising that a simple sum of losses works best among the tested rules. Table G1 gives a partial answer with an ablation of loss-combination rules, but it reports results only for PFSP. Is the behavior the same for other problems?

Q3: Did you consider using a more sophisticated loss, perhaps a weighted sum or a consistency loss? Another direction could be to exploit knowledge learned from both directions. There are many ways to do this, for example to select the better solution from the two directions and then imitate it in the other direction.

Q4: The paper repeatedly states that PDA improves the forward-only solver in 30 of 32 static-dual settings (and PDAT in 28–30 of 35), but no strong statistical analysis supports these counts, which could look like overclaiming. Every improvement is counted equally, although some are practically negligible (see the FJSP tables: some makespan improvements are less than 0.05%). Can you make this analysis statistically stronger and measure the significance of the improvements, e.g., by computing confidence intervals?

Q4: This work repeatedly states that PDA improves the forward-only solver in 30 of 32 static-dual settings (and PDAT in 28–30 of 35), but no strong statistical analysis supports these counts, which could look like overclaiming. Every improvement is counted equally, although some are practically negligible (see the FJSP tables: some makespan improvements are less than 0.05% and still they are considered as "better"). Can you make this analysis statistically stronger and measure the significance of the improvements, e.g., by computing confidence intervals?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 2xck: novelty, augmentation size, and when PDT helps

Thank you. You asked why dual training helps in some settings and not in others. We answer with a measured breakdown, and we have replaced the win counts with statistical tests, as you suggested (Q4).

Novelty. Duality is classical, as the paper says. Its use in NCO is not: to our knowledge no NCO method has used the dual to get more varied candidates at test time. For scheduling it is the only exact augmentation we know of, it works on any released checkpoint, and its gains are significant (general response, point 1).

Why PDAT is sometimes worse than PDA (Tables I3 and J6), and why ATSP benefits. Each column compares the forward-trained and the dual-trained model. How much PDA helps (last column) is the first column minus the second. Lower is better, except in the last column:

Backbone (learning method), metricWithout PDA: forward-trained → dual-trainedWith PDA: forward-trained → dual-trainedHow much PDA helps: forward-trained → dual-trained
GOAL (supervised), gap %4.67 → 4.203.62 → 3.271.05 → 0.93
MatPOENet (REINFORCE), tour length1.6551 → 1.62471.6365 → 1.61100.019 → 0.014
MP-ASIL, PFSP (self-imitation), makespan1237.39 → 1237.171237.06 → 1236.930.33 → 0.24
MP-ASIL, FFSP (self-imitation), makespan26.85 → 26.9026.75 → 26.700.10 → 0.20
MP-ASIL, JSSP (self-imitation), gap %8.47 → 8.767.89 → 8.070.58 → 0.69
  • ATSP (supervised). The dual of each training instance is one more exactly labeled example, so PDT doubles the labeled data for free. The model improves, by 0.47 here and by 0.31 in our second GOAL run. The PDA gain shrinks by less than that (0.12 here, 0.36 in the second run), so PDAT wins here and ties in the second run (3.42 vs. 3.47).
  • JSSP (self-imitation). The target is the best of the model's own samples, and PDT splits them: each direction imitates its best of K/2K/2 instead of KK, a weaker target. The model gets worse by 0.29, and PDAT loses.
  • PFSP, MatPOENet. The model improves, the PDA gain shrinks by 25–27%, and the two nearly cancel.
  • FJSP (Table J6). PGMPO also learns from the model's own samples, so it is in the self-imitation group. Its training effect is smaller than the variation between training runs, so the revision no longer claims it. On the same checkpoints the augmentation effect is reliable: it improves in 35 of 36 cases (Table J7) and is significant over 1,200 test instances (pp < 0.001).

So PDT helps when the dual adds training signal (supervised labels, REINFORCE samples) and not when it splits the model's own signal (self-imitation). The revision states this rule and recommends PDT with supervised or RL training and PDA alone with self-imitation.

Q1. Repeating full-budget JSSP training (about 8 hours per epoch) does not fit in the discussion period, so we mark single-run conclusions as such. The PDA conclusions do not depend on our training budgets: on the MP-ASIL authors' full-budget JSSP checkpoint, PDA lowers the gap from 7.69% to 7.01% (pp = 0.0001).

Q2. In every backbone, both directions use the backbone's own loss with the same kind of target, so the two terms are on the same scale. With supervised learning, the summed loss is simply the usual loss on a training set with twice as many labeled examples. With REINFORCE, each direction has its own baseline (the mean reward of its own samples), so the sum is the usual policy gradient over all samples. With self-imitation and preference learning, it is the average of two losses of the same kind. A weighted sum would only give one direction a larger share of each update, and no direction is better across problems. Table G1 tests the rules that change more than the weight, and both are worse: training only the better direction throws away half of the signal, and separate steps overfit. Where PDT falls short, the cause is the target each direction learns from, not how the two losses are combined.

Q3. We tested your suggestion on PFSP (20-epoch runs): both directions imitate the best solution found by either direction, the other direction learning the reversed sequence. With PDA it reaches 1241.74, worse than the summed loss (1240.91), and the PDA gain falls from 0.23 to 0.05: the two directions become almost the same model. Two related variants, one where the best solution trains only the direction that produced it and one with a direction embedding, also did not beat the summed loss (1241.78 and 1240.90) and shrank the gain (0.13 and 0.16). This confirms the second cost above: the more tightly the two directions are tied, the less PDA can add. A consistency loss would tie them even more tightly.

AuthorsOpenReview ↗

New comparison against larger sampling budgets

We have posted a new comparison under the general response ("Simple, but not replaceable by more sampling"): on the JSSP checkpoint released by the MP-ASIL authors, PDA with K candidates beats forward-only sampling with 2K candidates at every budget from 512 to 4,096, and matches or beats it at equal wall-clock. We think this bears on the question of what the augmentation adds beyond a simple extra input.

Dear authors,

Thank you very much for your response.

My concern about the statistics for PDA is largely resolved, and the PDA claim is now well supported. The provided tests show that the gain is real and is not just extra sampling.

However, my concerns about PDT remain. The results for PDT with GOAL are still confusing and depend largely on the training seed. The dual-trained model is better than the forward-trained one in only two of three runs, and the average effect is close to zero. The claim that PDT helps when “the dual adds training signal” seems arbitrary to me. It is still a hypothesis, and I do not see an experiment that tests it.

I think the real contribution of this paper is PDA, and that part works pretty well. PDT is better seen as a side finding that shows where training with duals can go wrong. If the paper is framed this way, the contribution becomes clear, but it remains incremental. For me, this makes the paper a borderline case.

I am open to discussing with the other reviewers and the AC to reach the best decision.

AuthorsOpenReview ↗

The revised PDF already adopts this framing

Thank you for reading the new results and for this assessment. We are glad that the statistical evidence for PDA now convinces you, and we want to point out that the revised PDF (please see "Revised PDF uploaded: summary of changes") already frames the paper in the way you describe.

PDA is the contribution. The introduction, the method section and the main experiments (Sections 1, 4.1 and 5.2–5.4) are about PDA alone: its effect on five problems, where the gain comes from, and what it costs.

PDT is reported as a secondary question with a negative answer. It occupies one subsection (5.5). With matched training budgets, PDAT is at best a tie with FWD+PDA over the three ATSP-GOAL runs and on the MP-ASIL backbones, and it is worse on JSSP. The paper no longer recommends PDT. The explanation that the dual "adds training signal" under supervised learning remains only as a description of the model used alone, and the third GOAL run is reported there as the exception to it. The mechanism the paper relies on is the one we measured rather than hypothesized: training one model on both directions makes the two directions more alike, so what PDT adds to the model it takes away from PDA (Table 5, and the extreme case in Table G2, where tying the directions together reduces the PDA gain from 0.23 to 0.05). The abstract and the conclusion were changed accordingly.

On incrementality, we would only add three points for you and the AC to weigh. To our knowledge, PDA is the first exact augmentation for job scheduling problems, which so far had none. It improves checkpoints released by other authors, with no retraining (Table 1). And its gain is not obtained by simply doubling the sampling budget: on the released JSSP checkpoint, PDA with K candidates beats forward-only decoding with 2K at every budget from 512 to 2,048 (Table 3).

Reviewer_oe6rOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This study shows how we can reverse classical preserved objective problems for neural combinatorial optimization. Their approach, problem-dual augmentation PDA, uses a solver on an instance and its dual, the reverse of a routing or scheduling to obtain solutions from an existing learned solver, usually splitting the fixed candidate budget. They also study problem-dual training PDT, which trains a shared model in both directions. Their methods are tested on ATSP problem and five other scheduling problems using four already published solvers. 5 of the problem classes has a static reversal instance, while the SMSP uses a backward decoder with an exact original-objective cost identity. The results show test-time reversal is dependent on the tested settings, while training on both directions is not.

Critical strengths
  1. The implementation of PDA improves an already trained model without changing its parameters or architecture. Their implementation is simple and straightforward. PDA reverses the problem and allocate candidate solutions to each direction, and keep the best answer. This method guarantees an exact solution obtained from the reversed problem, which can be mapped back with the same objective value.

  2. The study clearly separates augmentation from training. They clearly show that augmentation helps, but dual training partially reduces that benefit. The authors clearly identified which part of the method produces the benefit and finds the part where the additional training step is harmful.

Critical weaknesses
  1. The comparisons do not fully establish the practical advantage. The authors matches the number of candidates, but do not match the time or total training work. At inference, the same candidate can take longer time. The sequential implementations show there is significant overheads. These measurements also exclude construction of the dual instance, which the authors acknowledge is nontrivial for JSSP. The authors show that reversal can improve the use of a fixed candidate budget, but they do not consistently demonstrate better solution quality at the same computational cost.

  2. There are only a few runs for several training conclusions. The paper does not repeat training sufficiently across all configurations. The PFSP and JSSP only used one trained model per configuration. This weakens the conclusion that dual training may cause a significant improvement to problems. There is very little consistency across trained models.

Questions for authors
  1. How are the directional losses reduced?
  2. How much of MatPOENet’s improvement comes from dual training rather than additional training work
  3. Can you provide a comparison for PDA vs forward resampling on JSSP and FFSP, including dual construction and mapping back?
  4. Does PDA still outperform forward-only sampling when total inference time is equal?
3 comments
AuthorsOpenReview ↗

Response to Reviewer oe6r: inference time and training runs

Thank you. We have addressed both weaknesses with new measurements.

Inference time, including building the dual and mapping back. If the instance and its dual are decoded together in one batch, PDA costs little more time than FWD-only and still improves the result:

ProblemRelative inference time (vs. FWD-only)FWD-onlyFWD+PDA
FFSP, 20 jobs, 1,000 inst. (makespan)1.18× (one batch, building the dual included)26.8526.68
ATSP, MatPOENet, 1,000 inst. (tour length)1.06× (one batch)1.61451.6121
JSSP, Taillard, authors' MP-ASIL checkpoint (gap %)1.58× (building the dual included)7.697.01

The 2.07× in Appendix E came from decoding the two directions one after the other. Decoding them in one batch, as in all three rows, brings the cost down to 1.06–1.58×. No mapping back is needed to get the objective value: reversing a schedule in time gives a schedule for the original instance with the same cost. Re-scheduling the backward solutions on the original instance also does not change the result (6.48% with it, 6.35% without, on JSSP 15×15 and 50×20). In addition, on JSSP, PDA with KK candidates beats FWD-only with 2K2K candidates (7.79% vs. 8.11% at KK=512, Table 2).

Number of training runs. We now mark every conclusion that rests on a single run. The PDA conclusions rest on the paired tests above, which use fixed checkpoints and need no retraining. Repeat training runs for ATSP-GOAL are in progress.

Q1. We add the two directions' losses and take one optimizer step (Section 4). Appendix G compares this with separate steps and with updating only the better direction.

Q2 (MatPOENet). MatPOENet runs the two directions in one batch, so neither setting in Appendix F uses the same total training compute as FWD-only: one doubles the number of updates, the other doubles the number of rollouts. We do not have a FWD-only run with the same doubled compute, so we cannot separate the two effects. The revision treats MatPOENet as supporting evidence only and says so. Also, after dual training its PDA gain becomes smaller (1.12% → 0.84%), as point 2 of the general response predicts for RL.

Q3–Q4. See the inference-time table above.


AuthorsOpenReview ↗

New wall-clock comparison against larger sampling budgets

We have posted a new comparison under the general response ("Simple, but not replaceable by more sampling"): on the JSSP checkpoint released by the MP-ASIL authors, with both methods timed in the same run, PDA beats forward-only sampling at equal wall-clock at every budget from 1,024 to 4,096 candidates and ties it at 512, and the time ratio falls from 1.8× to 1.2× as the budget grows. We think this answers the wall-clock question directly.

Thank you for your rebuttal. I will maintain my positive score.

Comments on the paper

6 comments
AuthorsOpenReview ↗

General response (1/2): PDA gives significant gains with no training

We thank the reviewers. Our new results support two main points. We will upload a revised PDF built around them (one extra page in the main text, details in the appendices) during the discussion period.

  • PDA is simple, new to NCO, and improves trained models with no extra training. Problem duality is well known in OR. To our knowledge, it has not been used before to give learned solvers more varied candidate solutions at test time. PDA works on any released checkpoint, including for problems with no geometric augmentation. Its gains are statistically significant on JSSP, FFSP, FJSP and ATSP; on PFSP, where the forward-only model is already near the best-known solutions, the gain is small and not significant.
  • PDT helps when the dual adds training signal, and not when it splits it. With supervised learning, the dual of a labeled instance is labeled for free, so PDT doubles the labeled data at no labeling cost. With RL, the dual is one more instance with its own samples and baseline. In both, the model improves (GOAL in both training runs, MatPOENet). With self-imitation, the target is the best of the model's own KK samples; PDT splits them between two directions, so each direction learns from a weaker target, and the model does not improve. This is why PDAT is better than PDA on ATSP and not on JSSP.

1. PDA gives significant gains with no training (2xck Q4, oe6r). We now use statistical tests instead of counting wins. For each problem we run a two-sided paired Wilcoxon signed-rank test over the test instances (all methods are run on the same instances), at the 5% level, with 95% bootstrap confidence intervals for the mean difference. The table compares FWD-only and FWD+PDA on the same checkpoint:

ProblemFWD-only checkpointNumber of instancesDifference [95% CI]P-value
JSSP, 8 sizesMP-ASIL, released by authors80−0.68 [−1.00, −0.38]0.0001
JSSP, 8 sizesMP-ASIL, trained by us80−0.59 [−0.93, −0.27]0.0009
FFSP, 3 sizesMP-ASIL, trained by us3,000−0.167 [−0.210, −0.124]<0.001
FJSP, 12 sizesPGMPO, trained by us1,200−0.28 [−0.39, −0.16]<0.001
ATSP, 1 size (NN=100)GOAL, trained by us128−0.67 [−0.98, −0.39]<0.001
PFSP, 7 sizesMP-ASIL, trained by us70−0.075 [−0.155, −0.002]0.25

JSSP: Taillard benchmark, KK=512, difference in gap (%). FFSP: 20, 50 and 100 jobs, 1,000 instances each, KK=24, difference in makespan; each size is also significant on its own (pp = 0.026, 0.015, <0.001). FJSP: SD1 and SD2, six sizes each, 100 instances per size, difference in gap (%) to the reference solutions; each benchmark is also significant on its own (pp < 0.001 and pp = 0.0005). ATSP: GOAL decodes greedily, so PDA uses two calls (one per direction) and is compared with two forward calls; difference in gap (%). PFSP: On PFSP the gain is not significant because there is little left to improve: the FWD-only model is already within 1.8% of the best-known makespans on average, and within 0.1–0.5% on the 5-machine sizes. PDA still lowers the mean gap from 1.79% to 1.71%, as in the paper, but the per-instance chanTaillard benchmark, KK=128, per-instance gap averaged over five sampling runs. Negative means FWD+PDA is better. ges are too small to be significant. On the checkpoint released by the MP-ASIL authors, trained with their full budget, PDA lowers the Taillard gap from 7.69% to 7.01% with no retraining, at 1.58 times the inference time of FWD-only (see reply to oe6r). The gain does not come only from comparing at the same number of candidates. On JSSP, PDA with KK candidates beats FWD-only with twice as many candidates (2K2K, Table 2). In wall-clock time, PDA costs only 1.06 to 1.58 times FWD-only, including the time to build the dual instance. With only 10 Taillard instances per size, the per-size tests are significant at only some sizes, so we report the tests over all instances. In the revision, these tests replace the win counts, and differences that are not significant are reported as ties.

AuthorsOpenReview ↗

General response (2/2): When problem-dual training helps

2. When PDT helps (2xck, FGus, oe6r). The table shows the four variants from the paper's fully trained checkpoints:

Backbone (learning method), metricFWDFWD+PDAPDTPDAT
GOAL (supervised), gap %4.673.624.203.27
GOAL (supervised), second run4.743.424.433.47
MatPOENet (REINFORCE), tour length1.65511.63651.62471.6110
MP-ASIL, PFSP (self-imitation), makespan1237.391237.061237.171236.93
MP-ASIL, JSSP (self-imitation), gap %8.477.898.768.07
MP-ASIL, FFSP (self-imitation), makespan26.8526.7526.9026.70

Lower is better. PFSP: 1,000 in-distribution instances; JSSP: 80 Taillard instances, KK=512; FFSP: 1,000 instances, 20 jobs; GOAL: mean over five evaluation seeds; first run and MatPOENet from Tables I1 and F1.

Why PDT helps on ATSP and not on JSSP. PDT trains the model on both an instance and its dual. Whether this helps depends on where the training signal comes from.

  • Supervised (GOAL): the dual adds signal. The dual's label is the original label mapped through ϕ\phi, so it is exact and free. PDT doubles the labeled data without one extra LKH run. The model improves in both training runs (4.67 → 4.20, 4.74 → 4.43).
  • REINFORCE (MatPOENet): the dual adds signal. The dual is one more training instance with its own samples and its own baseline. The model improves (1.6551 → 1.6247).
  • Self-imitation (MP-ASIL): the dual splits the signal. The target is the best of the model's own KK samples. PDT gives each direction K/2K/2 samples, so each direction imitates the best of K/2K/2, a weaker target. The model gets worse on JSSP (8.47 → 8.76, mostly at sizes not seen in training, Section 5.4) and FFSP, and improves only slightly on PFSP.

Why PDAT is not always better than FWD+PDA. PDA works because the two directions produce different candidates. Training them together makes them more alike, so PDA adds less to a PDT model (GOAL: 1.05 → 0.93 and 1.33 → 0.97; MatPOENet and PFSP: 25–27% less). The extreme case confirms this: when both directions are trained on the same solution, the PDA gain almost vanishes (0.23 → 0.05; reply to 2xck, Q3). So PDAT beats FWD+PDA only when the model improves by more than the PDA gain shrinks. With supervised learning the model improves a lot, so PDAT wins (3.62 → 3.27) or ties (3.42 → 3.47). With self-imitation the model does not improve, so PDAT loses on JSSP (7.89 → 8.07) and ties on PFSP and FFSP.

In short: use PDT with supervised or RL training, where the dual is extra training data for free; with self-imitation, use PDA alone. The third GOAL run will be posted here.

AuthorsOpenReview ↗

Update: FJSP test results and the training variant suggested by Reviewer 2xck

We added the paired test on FJSP (1,200 instances; PDA is significant, pp < 0.001) to General response 1/2, and the result of the training variant suggested by Reviewer 2xck (Q3) to our replies to 2xck and FGus.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.