Recent trends in combinatorial optimization augmented machine learning: A graph learning perspective
summary
Describes embedding graph neural networks with a combinatorial optimization layer that predicts arc weights or customer prices and then decodes with MILP or genetic search, claims a practical win — won the 2022 EURO‑NeurIPS dynamic vehicle routing challenge — and replicates on about ten dynamic OR problems. Introduces a regularized Fenchel‑Young empirical cost minimization turned into an alternating minimization that converges under convexity assumptions, a sample‑based structured RL that optimizes over sampled candidate solutions, and a working autodiff ecosystem; trained on 50→5,000 instances for real generalization.
AI-written summary · about
chapters (14)
- 0:00Graph neural networks intro
- 2:09Predicting combinatorial objects
- 3:35Stochastic optimization apps
- 8:14Dynamic optimization challenges
- 11:54Decision-focused training
- 14:24Piecewise constant loss
- 17:33Fenchel-Young loss
- 20:31Cost minimization in optimization
- 27:21Exact algorithm properties
- 31:37Model bias and guarantees
- 32:20Dynamic vehicle routing
- 36:16Reinforcement learning layers
- 40:48Graph neural network apps
- 42:40Q&A
related talks
15mComputational Mobility: Learning, Prediction, and Algorithms
38mFusing Machine Learning and Mixed Integer Linear Programming
23mGraph ML – The Next Level Of Machine Learning; Learn How To Use It And When Not To
45mAGT and Machine Learning
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation II
06mDecoding the Maze: New Frontiers in Achieving Nash Equilibrium in AI Architectures
06mCloud-Native GraphRAG: AI’s Logical Edge