Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

By Zhuwen Li, Qifeng Chen, Vladlen Koltun. Neural Information Processing Systems, 2018

561 citations recorded by the source corpus.

We present a learning-based approach to computing solutions for certain NP-hard problems. Our approach combines deep learning techniques with useful algorithmic elements from classic heuristics. The central component is a graph convolutional network that is trained to estimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution. The network is designed and trained to synthesize a diverse set of solutions, which enables rapid exploration of the solution space via tree search. The presented approach is evaluated on four canonical NP-hard problems and five datasets, which include benchmark satisfiability problems and real social network graphs with up to a hundred thousand nodes. Experimental results demonstrate that the presented approach substantially outperforms recent deep learning work, and performs on par with highly optimized state-of-the-art heuristic solvers for some NP-hard problems. Experiments indicate that our approach generalizes across datasets, and scales to graphs that are orders of magnitude larger than those used during training.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/d77c0e84972c256a8922b952b04330e369f65f09

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Industrial and Manufacturing Engineering

Citations in the corpus

Solving Mixed Integer Programs Using Neural Networks (2020, methodology): “…has been applied to the Travelling Salesman Problem (Vinyals et al. 2015, Bello et al. 2016), Vehicle Routing (Kool et al. 2019, Nazari et al. 2018), Boolean Satisfiability (Selsam et al. 2019), and general graph-structured combinatorial optimization problems (Khalil et al. 2017a, Li et al. 2018).”
Finding key players in complex networks through deep reinforcement learning (2020, methodology): “Inspired by the recent advances in deep learning techniques for solving combinatorial optimization problems 19–24 , here we introduce FINDER (FInding key players in Networks through DEep Reinforcement learning), a generic and scalable deep reinforcement learning framework to find key players in…”
Learning to plan with uncertain topological maps (2020, unknown): “GNNs have been applied to shortest path planning in travelling salesmen problems [33,25] and it has been reasoned that they can approximate optimal symbolic planning algorithms such as the Bellman-Ford algorithm [60].”
DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization (2023, methodology): “The four learning-based methods can be divided into the reinforcement learning (RL) category, i.e., LwD [1]) and DIMES [92], and the supervised learning (SL) category, i.e., Intel [70] and DGL [8].”
Hypergraph Convolution and Hypergraph Attention (2019, background): “, 3D shape analysis [42, 68, 69], visual search [70], visual question answering [71], chemistry [27, 72], knowledge graphs [73], matrix factorization [74] and NP-hard problems [75].”
Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning (2020, background): “travelling salesman problem) [12, 13, 14, 15, 16, 17], graph optimization problems [18, 19], and the satisfiability problem (SAT) [20, 21, 22].”
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs (2018, methodology): “Inspired by the recent sucesses of deep graph models as learning-based approaches for NP-hard problems [31, 38, 26, 19], we have used HyperGCN as a learning-based approach for the densest k -subhypergraph problem [15].”
Differentiation of Blackbox Combinatorial Solvers (2019, background): “Some works have again targeted the TRAVELING-SALESMAN-PROBLEM [6, 9, 25] as well as other NP-Hard problems [27].”
Learning scheduling algorithms for data processing clusters (2018, background): “problems, such as vertex set cover and the traveling salesman problem [23, 49].”
What graph neural networks cannot learn: depth vs width (2019, methodology): “Further, there have been attempts to use GNNmp to devise heuristics for graph-based optimization problems (Khalil et al., 2017; Battaglia et al., 2018; Li et al., 2018; Joshi et al., 2019; Bianchi et al., 2019), such as the ones discussed above.”
Learning to simulate and design for structural engineering (2020, background): “Though some papers have applied GNNs to solve combinatorial optimization problems (Bello et al., 2016; Kool et al., 2018; Prates et al., 2019; Li et al., 2018), applying GNN to solve design optimization problem is underexplored.”
Deep Learning on Graphs: A Survey (2018, unknown): “…[137], [138], [139], gene expression [140], natural language processing (NLP) [141], [142], computer vision [143], [144], [145], [146], [147], trafﬁc forecasting [148], [149], program induction [150], solving graph-based NP problems [151], [152], and multi-agent AI systems [153], [154], [155].”
Learning a Neural Solver for Multiple Object Tracking (2019, methodology): “These methods have shown remarkable performance at a wide variety of areas, ranging from chemistry [23] to combinatorial optimization [45].”
Benchmarking Graph Neural Networks (2023, methodology): “For our experiments with TSP, we follow the learning-based approach to COPs described in (Li et al., 2018; Joshi et al., 2019), where a GNN is the backbone architecture for assignTable 4.”
Learning to Optimize: A Primer and A Benchmark (2021, background): “Lastly, let us mention recent works that leverage ML for combinatorial and discrete optimization [123; 61; 24; 25; 38].”