CaR: A New Approach for Constraint Handling in Neural Solvers

Neural solvers have demonstrated remarkable progress in addressing simple routing problems, particularly excelling in computational efficiency. However, their effectiveness in the presence of complex constraints is still limited. Current constraint-handling techniques, such as feasibility masking or implicit feasibility awareness, can be inefficient or inapplicable for hard constraints.

To address these challenges, Construct-and-Refine (CaR) has been presented, the first general and efficient framework for constraint handling in neural routing solvers, based on explicit learning-based feasibility refinement. Unlike existing construction-search hybrids, which aim to reduce optimality gaps through intensive improvements but struggle with hard constraints, CaR achieves efficient constraint handling by designing a joint training framework. This framework guides the construction module to generate diverse and high-quality solutions, suitable for a lightweight improvement process.

CaR also introduces the first use of a shared representation between construction and improvement, enabling potential knowledge sharing across paradigms by unifying the encoder, especially in more complex constrained scenarios. Evaluations on typical hard routing constraints demonstrate that CaR achieves superior feasibility, solution quality, and efficiency compared to both classical and neural state-of-the-art solvers.