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 Poster: Learning Physical Dynamics with Subequivariant Graph Neural Networks »
Jiaqi Han · Wenbing Huang · Hengbo Ma · Jiachen Li · Josh Tenenbaum · Chuang Gan -
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 -
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 -
2023 Poster: AVOIDDS: Aircraft Vision-based Intruder Detection Dataset and Simulator »
Elysia Smyers · Sydney Katz · Anthony Corso · Mykel J Kochenderfer -
2022 : Graph Q-Learning for Combinatorial Optimization »
Victoria Magdalena Dax · Jiachen Li · Kevin Leahy · Mykel J Kochenderfer -
2022 Spotlight: Learning Physical Dynamics with Subequivariant Graph Neural Networks »
Jiaqi Han · Wenbing Huang · Hengbo Ma · Jiachen Li · Josh Tenenbaum · Chuang Gan -
2022 Spotlight: Lightning Talks 4B-1 »
Alexandra Senderovich · Zhijie Deng · Navid Ansari · Xuefei Ning · Yasmin Salehi · Xiang Huang · Chenyang Wu · Kelsey Allen · Jiaqi Han · Nikita Balagansky · Tatiana Lopez-Guevara · Tianci Li · Zhanhong Ye · Zixuan Zhou · Feng Zhou · Ekaterina Bulatova · Daniil Gavrilov · Wenbing Huang · Dennis Giannacopoulos · Hans-peter Seidel · Anton Obukhov · Kimberly Stachenfeld · Hongsheng Liu · Jun Zhu · Junbo Zhao · Hengbo Ma · Nima Vahidi Ferdowsi · Zongzhang Zhang · Vahid Babaei · Jiachen Li · Alvaro Sanchez Gonzalez · Yang Yu · Shi Ji · Maxim Rakhuba · Tianchen Zhao · Yiping Deng · Peter Battaglia · Josh Tenenbaum · Zidong Wang · Chuang Gan · Changcheng Tang · Jessica Hamrick · Kang Yang · Tobias Pfaff · Yang Li · Shuang Liang · Min Wang · Huazhong Yang · Haotian CHU · Yu Wang · Fan Yu · Bei Hua · Lei Chen · Bin Dong -
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 Workshop: Machine Learning for Autonomous Driving »
Jiachen Li · Nigamaa Nayakanti · Xinshuo Weng · Daniel Omeiza · Ali Baheri · German Ros · Rowan McAllister -
2022 Workshop: Progress and Challenges in Building Trustworthy Embodied AI »
Chen Tang · Karen Leung · Leilani Gilpin · Jiachen Li · Changliu Liu -
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