Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time
Combinatorial optimization algorithms for graph problems are usually designed afresh for each new problem with careful attention by an expert to the problem structure. In this work, we develop a new framework to solve any combinatorial optimization problem over graphs that can be formulated as a single player game defined by states, actions, and rewards, including minimum spanning tree, shortest paths, traveling salesman problem, and vehicle routing problem, without expert knowledge. Our method trains a graph neural network using reinforcement learning on an unlabeled training set of graphs. The trained network then outputs approximate solutions to new graph instances in linear running time. In contrast, previous approximation algorithms or heuristics tailored to NP-hard problems on graphs generally have at least quadratic running time. We demonstrate the applicability of our approach on both polynomial and NP-hard problems with optimality gaps close to 1, and show that our method is able to generalize well: (i) from training on small graphs to testing on large graphs; (ii) from training on random graphs of one type to testing on random graphs of another type; and (iii) from training on random graphs to running on real world graphs.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationGraph Neural NetworkTraveling Salesman ProblemMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
Real-world decision-making systems are often subject to uncertainties that have to be resolved through observational data. Therefore, we are frequently confronted with combinatorial optimization problems of which the obj…
Combinatorial OptimizationDecision MakingSurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems
Optimization problems with nonlinear cost functions and combinatorial constraints appear in many real-world applications but remain challenging to solve efficiently compared to their linear counterparts. To bridge this g…
Combinatorial OptimizationSolving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning
Graph problems such as traveling salesman problem, or finding minimal Steiner trees are widely studied and used in data engineering and computer science. Typically, in real-world applications, the features of the graph t…
Combinatorial OptimizationDeep Reinforcement Learningreinforcement-learningReinforcement Learning (RL)+1Virtual Savant: learning for optimization
This article describes Virtual Savant, a novel paradigm that applies machine learning to derive knowledge from previously-solved optimization problem instances in order to solve new ones in a massively-parallel fashion. …
BIG-bench Machine LearningCombinatorial OptimizationNeural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization
Neural combinatorial optimization (NCO) is a promising learning-based approach for solving challenging combinatorial optimization problems without specialized algorithm design by experts. However, most constructive NCO m…
Combinatorial OptimizationDecoder