Fast and Parallel Algorithm for Neural Combinatorial Optimization with Constraints

Self-supervised learning for combinatorial optimization offers a promising way to train neural solvers without requiring optimal solutions as supervision. This requires informative gradients while respecting discrete feasibility. Recent geometric approaches use Carath\'eodory decompositions to decompose a neural network output into a distribution over feasible solutions, but the resulting decomposition procedures can be sequential and computationally expensive. We propose a parallel alternative based on linear optimization oracles. A neural network generates multiple query directions, whose samples are passed independently through the oracle to produce feasible solutions in parallel. We then obtain a probability distribution over these feasible solutions through a regularized simplex-constrained quadratic program and use its KKT conditions to derive the gradients of the designed loss, without differentiating through the discrete oracle. The resulting method relies mainly on parallel oracle calls and GPU-friendly linear algebra. Experiments across constrained combinatorial optimization problems show that it produces high-quality feasible solutions while substantially reducing the computational cost of decomposition-based self-supervised learning.