Source-linked AI summary
DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems
Ruizhong Qiu, Zhiqing Sun, Yiming Yang
TL;DR
Large-graph CO solvers face scalability limits from costly decoding and iterative refinement. DIMES replaces these operations with continuous candidate-distribution parameterization and meta-learning, and experiments report strong performance across TSP and MIS at scales reaching ten thousand nodes.
Problem
Existing DRL-based CO solvers face scalability challenges because costly decoding or iterative refinement becomes problematic on large graphs.
Method
DIMES uses a compact continuous parameterization for candidate-solution distributions, REINFORCE-based optimization, massively parallel sampling, and meta-learning for instance-specific initialization.
Results
DIMES outperforms strong DRL solvers on TSP and MIS while scaling to graphs with ten thousand nodes, whereas other strong solvers often fail to scale or produce significantly worse solutions.
Takeaways & Limitations
DIMES provides a unified approach for large-scale CO problems whose feasible solutions can be represented with 0/1-valued variables, including TSP and MIS.
Takeaways & Limitations
DIMES may have limited reasoning power because its continuous parameterization is generated in one shot, and extending it to multi-valued problems such as MIP is non-trivial.
Abstract
from arXiv · showhide
Recently, deep reinforcement learning (DRL) models have shown promising results in solving NP-hard Combinatorial Optimization (CO) problems. However, most DRL solvers can only scale to a few hundreds of nodes for combinatorial optimization problems on graphs, such as the Traveling Salesman Problem (TSP). This paper addresses the scalability challenge in large-scale combinatorial optimization by proposing a novel approach, namely, DIMES. Unlike previous DRL methods which suffer from costly autoregressive decoding or iterative refinements of discrete solutions, DIMES introduces a compact continuous space for parameterizing the underlying distribution of candidate solutions. Such a continuous space allows stable REINFORCE-based training and fine-tuning via massively parallel sampling. We further propose a meta-learning framework to enable the effective initialization of model parameters in the fine-tuning stage. Extensive experiments show that DIMES outperforms recent DRL-based methods on large benchmark datasets for Traveling Salesman Problems and Maximal Independent Set problems.
1 Introduction
CO problems have important applications but often incur exponential costs, while existing DRL solvers struggle to scale because decoding complete solutions creates overhead and sparse rewards. DIMES addresses this challenge with continuous solution parameterization, meta-learning, and large-scale experiments across TSP and MIS.
- CO has applications in shipment planning, transportation, robot routing, biology, and circuit design, but NP-hardness makes many problems exponentially costly for traditional algorithms.
- Existing DRL solvers learn CO patterns through construction heuristics that add nodes sequentially or improvement heuristics that iteratively refine feasible solutions.
- Costly solution decoding and delayed rewards make existing DRL methods difficult to scale to large graphs, including locally non-decomposable problems.
- DIMES parameterizes candidate-solution distributions in a compact continuous space, enabling massively parallel on-policy sampling and lower-variance REINFORCE gradients during training and fine-tuning.
- DIMES combines this parameterization with meta-learning across problem instances to initialize model parameters for effective instance-specific fine-tuning.
- DIMES outperforms strong DRL baselines on TSP and scales to graphs with tens of thousands of nodes, while achieving competitive performance on locally decomposable MIS problems.
2 Related Work
Prior DRL construction and improvement heuristics either decode solutions sequentially or refine them iteratively. DIMES instead samples from a continuous parameterization and uses meta-learning to train on large graphs directly.
- DRL-Based Construction Heuristics Learners: Construction heuristics produce CO solutions in one shot, whereas improvement heuristics repeatedly modify an existing solution using neural-network-guided local-search operations.
- DRL-Based Construction Heuristics Learners: DIMES differs from constructive MDP methods by parameterizing discrete candidate-solution distributions in a compact continuous space for efficient sampling without costly neural decoding.
- DRL-Based Construction Heuristics Learners: Locally decomposable problems have feasibility constraints and objectives that decompose over locally connected graph variables.
- DRL-Based Construction Heuristics Learners: DIMES uses meta-learning rather than a conventional DRL training framework, enabling training on large graphs directly.
- DRL-Based Construction Heuristics Learners: Earlier neural CO methods used supervision from optimal or approximate solutions, or predicted node and edge inclusion probabilities for MIS and TSP.
3 Proposed Method
DIMES parameterizes discrete combinatorial solutions with compact, continuous distributions and optimizes them using efficient sampling and REINFORCE-based updates. It further uses graph-neural-network meta-learning to initialize instance-specific fine-tuning.
- Formal Definitions: DIMES defines feasible solutions and their costs, then seeks an optimal solution by minimizing the cost over the feasible solution space.For TSP, solutions are tours; for MIS, they are independent subsets with cost given by the negated subset size.
- Continuous Parameterization: A continuous differentiable vector θ parameterizes solution probabilities, with higher θ_i values increasing the probability of including variable i.The variables are edges for TSP and nodes for MIS.
- Objective Optimization: For locally decomposable problems such as MIS, a penalty loss suppresses infeasible solutions, whereas general structured problems such as TSP require direct expected-cost optimization.TSP is described as having a global Hamiltonian-cycle constraint, so the penalty-based objective is not always applicable.
- Auxiliary Distributions: DIMES replaces inefficient energy-function sampling with an auxiliary distribution q_θ designed for efficient sampling and convergence to the same optimal parameters.The resulting objective supports REINFORCE-based gradient updates.
- Auxiliary Distribution for TSP: For TSP, θ is an n×n matrix over directed edges, and chain-rule factorization samples tours through node-visit permutations without MDP-based construction or MCMC sampling.A higher θ_i,j corresponds to a higher probability of sampling edge i to j.
- Meta-Learning: The meta-learning framework trains a GNN across problem instances and adapts its distribution parameters to each graph using gradient updates and a first-order MAML approximation.The procedure samples solutions, estimates gradients with REINFORCE, adapts parameters, and applies meta-updates; the convergence proof between p_θ and q_θ is deferred to the appendix.
4 Experiments
DIMES is evaluated on large-scale TSP and MIS benchmarks using solution quality, performance drop, and inference time. Experiments show strong results against learning-based and traditional baselines, while ablations identify the roles and trade-offs of meta-learning, fine-tuning, and continuous parameterization.
- Experimental Settings: DIMES is compared with 14 other TSP solvers using average tour length, performance drop, and total inference time.Length and Drop are lower-is-better metrics, while Time measures the total time to generate solutions for all test instances.
- TSP Main Results: DIMES significantly outperforms many previous learning-based methods and remains competitive with simple heuristics, despite using no ground-truth solutions.RL+AS+MCTS achieves the best performance but requires considerably more time; removing active search shortens runtime with only a slight performance drop.
- Ablation Study: Both inner gradient updates and inference-time fine-tuning are crucial to DIMES performance on TSP-1000.The paper attributes these effects to cross-instance generalization from meta-learning and instance-specific adaptation from fine-tuning.
- Ablation Study: Fine-tuning the GNN output and MLP parameters provides the best trade-off between universality and variance reduction.The study compares four fine-tuning choices, including the continuous parameterization alone and all GNN and MLP parameters.
- Ablation Study: More inner gradient updates improve test performance but consume more training time, creating a practical performance–training-time trade-off.This result is reported for TSP-1000 with greedy decoding across different values of T.
- MIS Main Results: DIMES outperforms prior baselines on medium-scale SATLIB and ER-[700-800] MIS datasets and significantly outperforms the supervised baseline on ER-[9000-11000].LwD performs better than DIMES on the largest ER setting, while DIMES is designed for general CO problems rather than locally decomposable MIS problems.
5 Conclusion & Discussion
DIMES combines compact continuous parameterization with meta-learning to solve large-scale TSP and MIS instances. The framework scales to graphs with ten thousand nodes while maintaining competitive solution quality, but its one-shot parameter generation limits reasoning power and broader applicability.
- Conclusion: DIMES combines compact continuous parameterization with a meta-learning strategy for large-scale TSP and MIS.The method is trained without ground-truth solutions and uses per-instance fine-tuning to improve solutions via local search.
- Conclusion: DIMES scales to graphs with ten thousand nodes, whereas other strong DRL solvers fail to scale or produce significantly worse solutions in most cases.
- Scope: The framework's generality assumes feasible solutions can be represented with 0/1-valued variables, such as selected nodes or edges.Applying DIMES to problems with multivalued variables, including Mixed Integer Programming, is non-trivial.
- Limitations: One-shot generation of the continuous parameterization can limit reasoning power, as observed in the MIS task.
- Decoding strategies: Parallel sampling, greedy decoding, and MCTS use the final continuous parameterization to search for feasible or high-quality solutions.Parallel sampling avoids repeatedly invoking neural networks after fine-tuning, while MCTS samples k-opt actions guided by the parameterization.
C.1 Neural Architecture for TSP
The TSP architecture uses an anisotropic graph neural network with edge gating, followed by an MLP that produces continuous parameters for graph edges. Because dense graphs are intractable at large scale, the method keeps only each node's k nearest neighbors.
- Anisotropic Graph Neural Networks: The TSP backbone is a 12-layer anisotropic GNN with width 32 and an edge-gating mechanism.Message passing uses node and edge features with learned layer parameters, aggregation, activation, normalization, and gating operations.
- Input features: Node and edge inputs are initialized from absolute node positions and absolute edge lengths.
- Output head: A 3-layer MLP with width 32 generates the final continuous parameterization for all edges.
- Graph Sparsification: Each node is connected only to its k nearest neighbors because dense connectivity grows quadratically with graph size and is intractable for large graphs.
C.2 Neural Architecture for MIS
The MIS architecture uses a graph convolutional network to score nodes, followed by a residual MLP that outputs the continuous parameterization for all nodes.
- Graph Convolutional Networks: The MIS backbone is a GCN whose input layer is initialized with all ones.
- Graph Convolutional Networks: GCN layers propagate node features using normalized adjacency-based convolutions with trainable weights and ReLU activation.
- Output head: A 10-layer residual MLP generates the final continuous parameterization for all nodes.
D Experimental Details
The experiments train DIMES with task-specific meta-gradient schedules, evaluate it on GPU and CPU setups, and provide public implementations and benchmark-generation details.
- TSP training: TSP training uses 120 meta-gradient steps for TSP-500 and TSP-1000, and 50 steps for TSP-10000.The reported training times are 1.5 hours, 1.7 hours, and 10 hours, respectively.
- Hardware: TSP evaluation runs learning-based methods on a GTX 1080 Ti GPU, while traditional algorithms use an Intel Xeon Gold 5118 CPU and MCTS uses an Intel Xeon Gold 6230 CPU.MCTS uses 64 threads for TSP-500 and TSP-1000, and 16 threads for TSP-10000.
- Reproduction: DIMES implementations for TSP and MIS are publicly available, with the TSP code released under an MIT license.
- MIS training: MIS experiments use 50k meta-gradient steps for SAT, 150k for ER-[700-800], and 200 additional steps for ER-[9000-11000] after checkpoint initialization.
- Datasets: SAT experiments use 39,500 training instances and 500 test instances, while Erdős-Rényi graphs are randomly generated for training and testing.
E.1 Convergence of Solution Distributions
DIMES’s auxiliary solution distribution qθ converges to the same solution as the target distribution pθ for both TSP and MIS under the stated conditions. The meta-gradient is also formally characterized, supporting the optimization framework.
- The propositions justify optimizing qθ instead of pθ because the two distributions converge to the same solution.
- If qθ assigns probability at least 1 − δ to a TSP solution, pθ assigns probability at least 1 − O(δ) to that solution.
- For MIS, the same convergence guarantee holds when θ is normalized and uniformly bounded with respect to each solution.
- As δ approaches zero, convergence of qθ to a solution implies convergence of pθ to that solution.
- The paper also gives a first-order approximation formula for the meta-gradient and evaluates DIMES with and without meta-learning on TSP-100.
F.2 Extrapolation Performance
DIMES is evaluated for extrapolation by training on TSP-100 and testing on larger graphs. Its performance does not drop much, indicating strong extrapolation across graph sizes.
- DIMES is trained on TSP-100 and tested on TSP-500, TSP-1000, and TSP-10000 without active search.
- The extrapolation results are compared with corresponding models trained directly on the larger TSP-n instances.
- DIMES’s performance does not drop much when trained on smaller graphs and tested on larger graphs.
F.3 Stability of Training
DIMES trains more stably and efficiently than AM and POMO in the reported comparisons. It reaches better performance in less time and with fewer training steps, while using only three instances per meta-gradient step.
- DIMES is much more sample-efficient than AM and POMO, achieving stable training with only 3 instances per meta-gradient descent step.
- DIMES’s total training time is shorter despite longer per-step time, and stable training permits a larger learning rate.
- In Figure 1, DIMES converges to better performance in less time, while AM and POMO train more slowly and less stably.
- DIMES also converges in fewer training steps than AM and POMO.