Timezone: »

 
Graph Q-Learning for Combinatorial Optimization
Victoria Magdalena Dax · Jiachen Li · Kevin Leahy · Mykel J Kochenderfer

Fri Dec 09 10:30 AM -- 10:45 AM (PST) @
in Graph Learning for Industrial Applications: Finance, Crime Detection, Medicine and Social Media »

Graph-structured data is ubiquitous throughout natural and social sciences, and Graph Neural Networks (GNNs) have recently been shown to be effective at solving prediction and inference problems on graph data. In this paper, we propose and demonstrate that GNNs can and should be applied to solve Combinatorial Optimization (CO) problems. Combinatorial Optimization (CO) concerns optimizing a function over a discrete solution space that is often intractably large. To learn to solve CO problems, we phrase specifying a candidate solution as a sequential decision making problem, where the return is related to how close the candidate solution is to optimality. We use a GNN to learn a policy to iteratively build increasingly promising candidate solutions. We present preliminary evidence that GNNs trained through Q-Learning can solve CO problems with performance approaching state-of-the-art heuristic-based solvers, using only a fraction of the parameters and training time.

Author Information

Victoria Magdalena Dax (Stanford University)
Jiachen Li (Stanford University)
Kevin Leahy (MIT Lincoln Laboratory)
Mykel J Kochenderfer (Stanford University)

More from the Same Authors