Neural solvers have demonstrated remarkable success in combinatorial optimization, often surpassing traditional heuristics in speed, solution quality, and generalization. However, their efficacy deteriorates significantly when confronted with complex constraints that cannot be effectively managed through simple masking mechanisms. To address this limitation, we introduce Universal Constrained Preference Optimization (UCPO), a novel plug-and-play framework that seamlessly integrates preference learning into existing neural solvers via a specially designed loss function, without requiring architectural modifications. UCPO embeds constraint satisfaction directly into a preference-based objective, eliminating the need for meticulous hyperparameter tuning. Leveraging a lightweight warm-start fine-tuning protocol, UCPO enables pre-trained models to consistently produce near-optimal, feasible solutions on challenging constraint-laden tasks, achieving exceptional performance with as little as 1% of the original training budget.

Pickup and Delivery Problem with Time Windows (PDPTW) is a prevalent research direction in modern logistics transportation. In this challenging problem, customers are divided into pickup nodes and delivery nodes, and vehicles must first serve each pickup node before proceeding to its corresponding delivery node. Moreover, the hard time window constraint presents an obstacle for the existing learning-to-construct methods. Hence, this paper proposes a novel learning-to-construct approach based on node-pair insertion to address the complex time window constraint. It involves predicting the insertion point for the next node pair within the current partial solution and ensuring constraint adherence. We enhance the context information for the decoder to produce better solutions. The experimental results verify that the proposed approach can construct high-quality solutions in a very short period of time.

Thanks to the highly-expressive generative capabilities exhibited by diffusion models, recent works have shown their promising performance in combinatorial optimization (CO) problems, where the complicated problems are converted into the corrupting and denoising of heatmaps. The characteristics of diffusion-based approaches result in special advantages for Multi-Objective CO (MOCO) problems, especially MultiObjective Traveling Salesman Problem (MOTSP) better aligned with that solving paradigm. In this paper, we improve and adapt the diffusion-based approaches to tackle MOTSP, which are trained to generate various Pareto optimal solutions according to the problem decomposition strategies. Experimental results demonstrate that although the proposed approach may lag behind with the most advanced neural methods at present, it outperforms several traditional heuristics with a single graph neural network, indicating its effectiveness and potentiality in addressing MOCO problems.