Search

Single-stage neural combinatorial optimization solvers have achieved near-optimal results on various small-scale combinatorial optimization (CO) problems without requiring expert knowledge. However, these solvers exhibit significant performance degradation when applied to large-scale CO problems. Recently, two-stage neural methods motivated by divide-and-conquer strategies have shown efficiency in addressing large-scale CO problems. Nevertheless, the performance of these methods highly relies on problem-specific heuristics in either the dividing or the conquering procedure, which limits their applicability to general CO problems. Moreover, these methods employ separate training schemes and ignore the interdependencies between the dividing and conquering strategies, often leading to sub-optimal solutions. To tackle these drawbacks, this article develops a unified neural divide-and-conquer framework (i.e., UDC) for solving general large-scale CO problems. UDC offers a Divide-Conquer-Reunion (DCR) training method to eliminate the negative impact of a sub-optimal dividing policy. Employing a high-efficiency Graph Neural Network (GNN) for global instance dividing and a fixed-length sub-path solver for conquering divided sub-problems, the proposed UDC framework demonstrates extensive applicability, achieving superior performance in 10 representative large-scale CO problems. The code is available at https://github.com/CIAM-Group/NCO_code/tree/main/single_objective/UDC-Large-scale-CO-master.

The neural combinatorial optimization (NCO) approach has shown great potential for solving routing problems without the requirement of expert knowledge. However, existing constructive NCO methods cannot directly solve large-scale instances, which significantly limits their application prospects. To address these crucial shortcomings, this work proposes a novel Instance-Conditioned Adaptation Model (ICAM) for better large-scale generalization of neural combinatorial optimization. In particular, we design a powerful yet lightweight instance-conditioned adaptation module for the NCO model to generate better solutions for instances across different scales. In addition, we develop an efficient three-stage reinforcement learning-based training scheme that enables the model to learn cross-scale features without any labeled optimal solution. Experimental results show that our proposed method is capable of obtaining excellent results with a very fast inference time in solving Traveling Salesman Problems (TSPs) and Capacitated Vehicle Routing Problems (CVRPs) across different scales. To the best of our knowledge, our model achieves state-of-the-art performance among all RL-based constructive methods for TSP and CVRP with up to 1,000 nodes., Comment: 17 pages, 6 figures

Neural construction models have shown promising performance for Vehicle Routing Problems (VRPs) by adopting either the Autoregressive (AR) or Non-Autoregressive (NAR) learning approach. While AR models produce high-quality solutions, they generally have a high inference latency due to their sequential generation nature. Conversely, NAR models generate solutions in parallel with a low inference latency but generally exhibit inferior performance. In this paper, we propose a generic Guided Non-Autoregressive Knowledge Distillation (GNARKD) method to obtain high-performance NAR models having a low inference latency. GNARKD removes the constraint of sequential generation in AR models while preserving the learned pivotal components in the network architecture to obtain the corresponding NAR models through knowledge distillation. We evaluate GNARKD by applying it to three widely adopted AR models to obtain NAR VRP solvers for both synthesized and real-world instances. The experimental results demonstrate that GNARKD significantly reduces the inference time (4-5 times faster) with acceptable performance drop (2-3\%). To the best of our knowledge, this study is first-of-its-kind to obtain NAR VRP solvers from AR ones through knowledge distillation., Comment: 11 pages, 5 figures, accepted by AAAI24

The paper is concerned about a sharp form of Anisotropic Moser-Trudinger inequality which involves $L^{n}$ norm. Let \begin{equation*} \lambda_{1}(\Omega) = \inf_{u\in W_0^{1,n}(\Omega),u\not\equiv 0} ||F(\nabla u)||_{L^n(\Omega)}^n / ||u||_{L^n(\Omega)}^n \end{equation*} be the first eigenvalue associated with $n$-Finsler-Laplacian. using blowing up analysis, we obtain that \begin{equation*} \sup_{u\in W_{0}^{1,n}(\Omega),||F(\nabla u)||_{L^n(\Omega)} = 1} \int_{\Omega}e^{\lambda_n (1+\alpha||u||_{L^n (\Omega)}^n)^{\frac{1}{n-1}} |u|^{\frac{n}{n-1}}}dx \end{equation*} is finite for any $0\leq \alpha<\lambda_{1}(\Omega)$,and the supremum is infinite for any $\alpha\geq \lambda_{1}(\Omega)$, where $\lambda_{n} = n^{\frac{n}{n-1}} \kappa_n^{\frac{1}{n-1}}$ ($\kappa_{n}$ is the volume of the unit wulff ball) and the function $F$ is positive,convex and homogeneous of degree $1$, and its polar $F^o$ represents a Finsler metric on $\mathbb{R}^n$. Furthermore, the supremum is attained for any $0\leq \alpha<\lambda_{1}(\Omega)$.