Problem-Dual Augmentation and Training for Neural Combinatorial Optimization

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.