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.

Recent decomposition-based neural multi-objective combinatorial optimization (MOCO) methods struggle to achieve desirable performance. Even equipped with complex learning techniques, they often suffer from significant optimality gaps in weight-specific subproblems. To address this challenge, we propose a neat weight embedding method to learn weight-specific representations, which captures weight-instance interaction for the subproblems and was overlooked by most current methods. We demonstrate the potentials of our method in two instantiations. First, we introduce a succinct addition model to learn weight-specific node embeddings, which surpassed most existing neural methods. Second, we design an enhanced conditional attention model to simultaneously learn the weight embedding and node embeddings, which yielded new state-of-the-art performance. Experimental results on classic MOCO problems verified the superiority of our method. Remarkably, our method also exhibits favorable generalization performance across problem sizes, even outperforming the neural method specialized for boosting size generalization.

Existing neural multi-objective combinatorial optimization (MOCO) methods still exhibit an optimality gap since they fail to fully exploit the intrinsic features of problem instances. A significant factor contributing to this shortfall is their reliance solely on graph-modal information. To overcome this, we propose a novel graph-image multimodal fusion (GIMF) framework that enhances neural MOCO methods by integrating graph and image information of the problem instances. Our GIMF framework comprises three key components: (1) a constructed coordinate image to better represent the spatial structure of the problem instance, (2) a problem-size adaptive resolution strategy during the image construction process to improve the cross-size generalization of the model, and (3) a multimodal fusion mechanism with modality-specific bottlenecks to efficiently couple graph and image information. We demonstrate the versatility of our GIMF by implementing it with two state-of-the-art neural MOCO backbones. Experimental results on classic MOCO problems show that our GIMF significantly outperforms state-of-the-art neural MOCO methods and exhibits superior generalization capability.

Neural Combinatorial Optimization (NCO) has emerged as a promising approach for NP-hard problems. However, prevailing RL-based methods suffer from low sample efficiency due to sparse rewards and underused solutions. We propose Best-anchored and Objective-guided Preference Optimization (BOPO), a training paradigm that leverages solution preferences via objective values. It introduces: (1) a best-anchored preference pair construction for better explore and exploit solutions, and (2) an objective-guided pairwise loss function that adaptively scales gradients via objective differences, removing reliance on reward models or reference policies. Experiments on Job-shop Scheduling Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP) show BOPO outperforms state-of-the-art neural methods, reducing optimality gaps impressively with efficient inference. BOPO is architecture-agnostic, enabling seamless integration with existing NCO models, and establishes preference optimization as a principled framework for combinatorial optimization.

Pedestrian trajectory prediction aims to forecast future trajectories based on observed behaviors and surrounding conditions, and it is critical for applications like autonomous driving. Predicting trajectories in unseen scenes is challenging due to varying environments, elusive internal movement patterns, and complex social interactions. Existing methods face two limitations. Firstly, they struggle to effectively extract internal movement patterns from historical trajectories without labeled samples, which are often inaccessible in practice. Secondly, they fail to learn social interaction patterns across scenes, particularly when using angle-related features that are noise-sensitive and not strictly invariant to Euclidean transformations. To address these challenges, this paper introduces a Geometry-guided Behavior Pattern Adaptation (GBPA) method based on two geometric observations. Firstly, properly normalized historical trajectories are distributionally similar to full trajectories, allowing generation of pseudo-full trajectories for auxiliary training. Secondly, the discretized angular partitions, created by splitting the perceptive field into equal-sized fans, are invariant to Euclidean transformations and robust to noise. GBPA employs a test-time training strategy on scaled historical trajectories (T3SH) to adapt internal movement patterns without future trajectories and an angular partitioned attention (APA) mechanism to capture transferable social interaction patterns by differentiating neighbors’ effects. Experimental results on two datasets demonstrate that GBPA significantly improves prediction performance.

Recent deep reinforcement learning methods have achieved remarkable success in solving multi-objective combinatorial optimization problems (MOCOPs) by decomposing them into multiple subproblems, each associated with a specific weight vector. However, these methods typically treat all subproblems equally and solve them using a single model, hindering the effective exploration of the solution space and thus leading to suboptimal performance. To overcome the limitation, we propose POCCO, a novel plug-and-play framework that enables adaptive selection of model structures for subproblems, which are subsequently optimized based on preference signals rather than explicit reward values. Specifically, we design a conditional computation block that routes subproblems to specialized neural architectures. Moreover, we propose a preference-driven optimization algorithm that learns pairwise preferences between winning and losing solutions. We evaluate the efficacy and versatility of POCCO by applying it to two state-of-the-art neural methods for MOCOPs. Experimental results across four classic MOCOP benchmarks demonstrate its significant superiority and strong generalization.

We consider the robust routing problem with uncertain travel times under the min-max regret criterion, which represents an extended and robust version of the classic traveling salesman problem (TSP) and vehicle routing problem (VRP). The general budget uncertainty set is employed to capture the uncertainty, which provides the capability to control the conservatism of obtained solutions and covers the commonly used interval uncertainty set as a special case. The goal is to obtain a robust solution that minimizes the maximum deviation from the optimal routing time in the worst-case scenario. Given the significant advancements and broad applications of neural combinatorial optimization methods in recent years, we present our initial attempt to combine neural approaches for solving this problem. We propose a dual multi-head cross attention mechanism to extract problem features represented by the inputted uncertainty sets. To tackle the built-in maximization problem, we derive the regret value by invoking a pre-trained model, subsequently utilizing it as the reward during the model training. Our experimental results on the robust TSP and VRP demonstrate the efficacy of our neural combinatorial optimization method, showcasing its ability to efficiently handle the robust routing problem of various sizes within a shorter time compared with alternative heuristic approaches.

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.

We explore the robust traveling salesman problem (RTSP) with interval uncertainty under the min-max regret criterion, which enhances the classic traveling salesman problem (TSP) by focusing on robustness. Our aim is to develop a conservative solution that minimizes the maximum deviation from the optimal routing time in the worst-case scenario. To achieve this, we integrate neural models into heuristic approaches, capitalizing on recent advancements in neural techniques. Specifically, we incorporate a pre-trained neural model into the tabu search framework, using it to refine the evaluation function. This novel integration streamlines the solution improvement process. Our experimental results underscore the effectiveness of this approach, showing that it handles various scales of the robust traveling salesman problem more efficiently and in less time compared to traditional heuristic methods.

Recently, neural heuristics based on deep reinforcement learning have exhibited promise in solving multi-objective combinatorial optimization problems (MOCOPs). However, they are still struggling to achieve high learning efficiency and solution quality. To tackle this issue, we propose an efficient meta neural heuristic (EMNH), in which a meta-model is first trained and then fine-tuned with a few steps to solve corresponding single-objective subproblems. Specifically, for the training process, a (partial) architecture-shared multi-task model is leveraged to achieve parallel learning for the meta-model, so as to speed up the training; meanwhile, a scaled symmetric sampling method with respect to the weight vectors is designed to stabilize the training. For the fine-tuning process, an efficient hierarchical method is proposed to systematically tackle all the subproblems. Experimental results on the multi-objective traveling salesman problem (MOTSP), multi-objective capacitated vehicle routing problem (MOCVRP), and multi-objective knapsack problem (MOKP) show that, EMNH is able to outperform the state-of-the-art neural heuristics in terms of solution quality and learning efficiency, and yield competitive solutions to the strong traditional heuristics while consuming much shorter time.

Most of existing neural methods for multi-objective combinatorial optimization (MOCO) problems solely rely on decomposition, which often leads to repetitive solutions for the respective subproblems, thus a limited Pareto set. Beyond decomposition, we propose a novel neural heuristic with diversity enhancement (NHDE) to produce more Pareto solutions from two perspectives. On the one hand, to hinder duplicated solutions for different subproblems, we propose an indicator-enhanced deep reinforcement learning method to guide the model, and design a heterogeneous graph attention mechanism to capture the relations between the instance graph and the Pareto front graph. On the other hand, to excavate more solutions in the neighborhood of each subproblem, we present a multiple Pareto optima strategy to sample and preserve desirable solutions. Experimental results on classic MOCO problems show that our NHDE is able to generate a Pareto front with higher diversity, thereby achieving superior overall performance. Moreover, our NHDE is generic and can be applied to different neural methods for MOCO.

Recent neural methods for vehicle routing problems always train and test the deep models on the same instance distribution (i.e., uniform). To tackle the consequent cross-distribution generalization concerns, we bring the knowledge distillation to this field and propose an Adaptive Multi-Distribution Knowledge Distillation (AMDKD) scheme for learning more generalizable deep models. Particularly, our AMDKD leverages various knowledge from multiple teachers trained on exemplar distributions to yield a light-weight yet generalist student model. Meanwhile, we equip AMDKD with an adaptive strategy that allows the student to concentrate on difficult distributions, so as to absorb hard-to-master knowledge more effectively. Extensive experimental results show that, compared with the baseline neural methods, our AMDKD is able to achieve competitive results on both unseen in-distribution and out-of-distribution instances, which are either randomly synthesized or adopted from benchmark datasets (i.e., TSPLIB and CVRPLIB). Notably, our AMDKD is generic, and consumes less computational resources for inference.

The multiobjective combinatorial optimization problems (MOCOPs) have a wide range of real-world applications. Designing an effective algorithm has an important and practical significance. Due to the huge search space and limited time, it is generally difficult to obtain the optimal solution of this kind of problem by traditional exact and heuristic algorithms. Recently, learning-based algorithms have achieved good results in solving MOCOPs, but the quality and diversity of found solutions can be further improved. In this paper, we propose a Weight-Specific-Decoder Attention Model (WSDAM) to better approximate the whole Pareto set. It embeds a weight-adaptive layer into the decoder to concentrate on the information of different weight vectors. During the model training, the weight vector is sampled from the Dirichlet distribution, which can further strengthen the learning of boundary solutions. We evaluate our method on two classic MOCOPs, i.e., the multiobjective traveling salesman problem (MOTSP) and multiobjective capacitated vehicle routing problem (MOCVRP). The experimental results show that our proposed method outperforms current state-of-the-art learning-based methods in both solution quality and generalization ability.

There are many combinatorial optimization problems derived from the classic traveling salesman problem (TSP). The quadratic traveling salesman problem (QTSP) is one of them. It needs to consider the relationship between three successive nodes rather than two successive nodes. In literature, there are exact methods based on integer programming and approximate methods based on heuristics for solving QTSP. In this paper, we try to adopt deep reinforcement learning to tackle QTSP. We consider two classic QTSPs studied in the previous literature, namely the angular-metric TSP and the angular-distance-metric TSP. Both of them consider the turning angle for each node, and the angular-distance-metric TSP further considers the total traveling distance in the original TSP. The experimental results show that our method is superior to some typical heuristic methods in terms of solution quality, and better than the exact methods in terms of time.

Locating individual congested links in large scale networks is an important but difficult problem, because of the hardness to directly measure the massive links. Current advantages of network tomography propose to infer the link congestion states by end-to-end measurements via solving a set of linear equations in Boolean algebra. But one challenging problem in such approaches is the requirement to construct n linearly independent measurements for uniquely identifying the states of n links. It is especially cost inefficient when the congested links are sparse, but requiring larger than n measurements to form a full-rank observation matrix. In this paper, we focus on efficient methods to take only limited number of path measurements to locate the sparsely congested links. To avoid the ambiguity of solving the boolean equations, at first, we propose a compressive sensing method to estimate the congestion probabilities of the individual links based on the deficient measurements (routing matrix is not full rank). Based on the congestion probability estimation, a greedy iterative estimation algorithm is developed to locate the congested links by online snapshot of the deficient measurements. Extensive simulations shows the effectiveness of proposed methods which reduce the measurement costs while preserving the detection accuracy.