Timezone: »

 
Poster
DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems
Ruizhong Qiu · Zhiqing Sun · Yiming Yang

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #128
in Poster Session 6 »

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.

Keywords: Combinatorial Optimization · meta learning · Graph neural network · Minimum Indepedent Set (MIS) · Traveling Salesman Problem (TSP)
[ Paper]  [ Slides]  [ Poster]  [ OpenReview] 

Author Information

Ruizhong Qiu (University of Illinois Urbana-Champaign)
Zhiqing Sun (Carnegie Mellon University)
Yiming Yang (CMU)

More from the Same Authors