Timezone: »
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
-
2021 : WildfireDB: An Open-Source Dataset Connecting Wildfire Occurrence with Relevant Determinants »
Samriddhi Singla · Ayan Mukhopadhyay · Michael Wilbur · Tina Diao · Vinayak Gajjewar · Ahmed Eldawy · Mykel J Kochenderfer · Ross Shachter · Abhishek Dubey -
2022 : A POMDP Model for Safe Geological Carbon Sequestration »
Anthony Corso · Yizheng Wang · Markus Zechner · Jef Caers · Mykel J Kochenderfer -
2022 : Fifteen-minute Competition Overview Video »
Nathan Drenkow · Raman Arora · Gino Perrotta · Todd Neller · Ryan Gardner · Mykel J Kochenderfer · Jared Markowitz · Corey Lowman · Casey Richardson · Bo Li · Bart Paulhamus · Ashley J Llorens · Andrew Newman -
2022 : Graph Q-Learning for Combinatorial Optimization »
Victoria Magdalena Dax · Jiachen Li · Kevin Leahy · Mykel J Kochenderfer -
2023 Poster: AVOIDDS: Aircraft Vision-based Intruder Detection Dataset and Simulator »
Elysia Smyers · Sydney Katz · Anthony Corso · Mykel J Kochenderfer -
2023 Poster: Conformal Prediction for Uncertainty-Aware Planning with Diffusion Dynamics Model »
Jiankai Sun · Yiqi Jiang · Jianing Qiu · Parth Nobel · Mykel J Kochenderfer · Mac Schwager -
2022 Competition: Reconnaissance Blind Chess: An Unsolved Challenge for Multi-Agent Decision Making Under Uncertainty »
Ryan Gardner · Gino Perrotta · Corey Lowman · Casey Richardson · Andrew Newman · Jared Markowitz · Nathan Drenkow · Bart Paulhamus · Ashley J Llorens · Todd Neller · Raman Arora · Bo Li · Mykel J Kochenderfer -
2022 Poster: Collaborative Decision Making Using Action Suggestions »
Dylan Asmar · Mykel J Kochenderfer -
2022 Poster: Interaction Modeling with Multiplex Attention »
Fan-Yun Sun · Isaac Kauvar · Ruohan Zhang · Jiachen Li · Mykel J Kochenderfer · Jiajun Wu · Nick Haber -
2022 Poster: Risk-Driven Design of Perception Systems »
Anthony Corso · Sydney Katz · Craig Innes · Xin Du · Subramanian Ramamoorthy · Mykel J Kochenderfer -
2021 Poster: Evidential Softmax for Sparse Multimodal Distributions in Deep Generative Models »
Phil Chen · Masha Itkina · Ransalu Senanayake · Mykel J Kochenderfer -
2021 : Reconnaissance Blind Chess + Q&A »
Ryan Gardner · Gino Perrotta · Corey Lowman · Casey Richardson · Andrew Newman · Jared Markowitz · Nathan Drenkow · Bart Paulhamus · Ashley J Llorens · Todd Neller · Raman Arora · Bo Li · Mykel J Kochenderfer -
2020 Poster: Handling Missing Data with Graph Representation Learning »
Jiaxuan You · Xiaobai Ma · Yi Ding · Mykel J Kochenderfer · Jure Leskovec -
2020 Poster: Evidential Sparsification of Multimodal Latent Spaces in Conditional Variational Autoencoders »
Masha Itkina · Boris Ivanovic · Ransalu Senanayake · Mykel J Kochenderfer · Marco Pavone -
2020 Poster: Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration »
Andrea Zanette · Alessandro Lazaric · Mykel J Kochenderfer · Emma Brunskill -
2019 Poster: Almost Horizon-Free Structure-Aware Best Policy Identification with a Generative Model »
Andrea Zanette · Mykel J Kochenderfer · Emma Brunskill -
2019 Poster: Limiting Extrapolation in Linear Approximate Value Iteration »
Andrea Zanette · Alessandro Lazaric · Mykel J Kochenderfer · Emma Brunskill -
2018 Poster: Deep Dynamical Modeling and Control of Unsteady Fluid Flows »
Jeremy Morton · Antony Jameson · Mykel J Kochenderfer · Freddie Witherden -
2018 Poster: Amortized Inference Regularization »
Rui Shu · Hung Bui · Shengjia Zhao · Mykel J Kochenderfer · Stefano Ermon -
2016 : Building and Validating the AI behind the Next-Generation Aircraft Collision Avoidance System »
Mykel J Kochenderfer