# Learning for Robust Combinatorial Optimization: Algorithm and Application

arXiv: https://arxiv.org/abs/2112.10377 · HTML: https://mlsanity.com/paper/2112.10377/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 53 references that are in the map.
- First posted on arXiv 20 Dec 2021.

## Builds on (most cited first, 26 of 26)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [Learning Scheduling Algorithms for Data Processing Clusters](https://mlsanity.com/paper/1810.01963/) (2018)
- [Learned Optimizers that Scale and Generalize](https://mlsanity.com/paper/1703.04813/) (2017)
- [Learning to Optimize: Training Deep Neural Networks for Wireless Resource Management](https://mlsanity.com/paper/1705.09412/) (2017)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [Towards Optimal Power Control via Ensembling Deep Neural Networks](https://mlsanity.com/paper/1807.10025/) (2018)
- [On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach](https://mlsanity.com/paper/1910.07512/) (2019)
- [Training Stronger Baselines for Learning to Optimize](https://mlsanity.com/paper/2010.09089/) (2020)
- [Learning to Optimize in Swarms](https://mlsanity.com/paper/1911.03787/) (2019)
- [Improved Adversarial Training via Learned Optimizer](https://mlsanity.com/paper/2004.12227/) (2020)
- [Exploiting Vulnerabilities of Load Forecasting Through Adversarial Attacks](https://mlsanity.com/paper/1904.06606/) (2019)
- [ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems](https://mlsanity.com/paper/1905.10899/) (2019)
- [Robust Submodular Maximization: A Non-Uniform Partitioning Approach](https://mlsanity.com/paper/1706.04918/) (2017)
- [Robust Monotone Submodular Function Maximization](https://mlsanity.com/paper/1507.06616/) (2015)
- [Task Offloading and Replication for Vehicular Cloud Computing: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/1812.04575/) (2018)
- [K-Beam Minimax: Efficient Optimization for Deep Adversarial Learning](https://mlsanity.com/paper/1805.11640/) (2018)

## Built on by (most cited first, 4 of 4)

- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [Neur2SP: Neural Two-Stage Stochastic Programming](https://mlsanity.com/paper/2205.12006/) (2022)
- [Learning-Augmented Decentralized Online Convex Optimization in Networks](https://mlsanity.com/paper/2306.10158/) (2023)
- [Low-Latency Relay Selection in NR-V2X Vehicular Communications via Graph Isomorphism Networks with Edge Features](https://mlsanity.com/paper/2607.14176/) (2026)

## Abstract (arXiv)

Learning to optimize (L2O) has recently emerged as a promising approach to solving optimization problems by exploiting the strong prediction power of neural networks and offering lower runtime complexity than conventional solvers. While L2O has been applied to various problems, a crucial yet challenging class of problems -- robust combinatorial optimization in the form of minimax optimization -- have largely remained under-explored. In addition to the exponentially large decision space, a key challenge for robust combinatorial optimization lies in the inner optimization problem, which is typically non-convex and entangled with outer optimization. In this paper, we study robust combinatorial optimization and propose a novel learning-based optimizer, called LRCO (Learning for Robust Combinatorial Optimization), which quickly outputs a robust solution in the presence of uncertain context. LRCO leverages a pair of learning-based optimizers -- one for the minimizer and the other for the maximizer -- that use their respective objective functions as losses and can be trained without the need of labels for training problem instances. To evaluate the performance of LRCO, we perform simulations for the task offloading problem in vehicular edge computing. Our results highlight that LRCO can greatly reduce the worst-case cost and improve robustness, while having a very low runtime complexity.