# Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 79 references that are in the map.
- First posted on arXiv 22 Oct 2023.

## Builds on (most cited first, 30 of 47)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Random Erasing Data Augmentation](https://mlsanity.com/paper/1708.04896/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [CURL: Contrastive Unsupervised Representations for Reinforcement Learning](https://mlsanity.com/paper/2004.04136/) (2020)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Image Augmentation Is All You Need: Regularizing Deep Reinforcement Learning from Pixels](https://mlsanity.com/paper/2004.13649/) (2020)
- [Reinforcement Learning with Augmented Data](https://mlsanity.com/paper/2004.14990/) (2020)
- [Generalizing to Unseen Domains via Adversarial Data Augmentation](https://mlsanity.com/paper/1805.12018/) (2018)
- [The Effectiveness of Data Augmentation in Image Classification using Deep Learning](https://mlsanity.com/paper/1712.04621/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [A Kernel Theory of Modern Data Augmentation](https://mlsanity.com/paper/1803.06084/) (2018)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Graph Adversarial Training: Dynamically Regularizing Based on Graph Structure](https://mlsanity.com/paper/1902.08226/) (2019)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies](https://mlsanity.com/paper/2002.05120/) (2020)
- [Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation](https://mlsanity.com/paper/2210.07686/) (2022)
- [On the Generalization Effects of Linear Transformations in Data Augmentation](https://mlsanity.com/paper/2005.00695/) (2020)
- [Learning to Schedule Heuristics in Branch-and-Bound](https://mlsanity.com/paper/2103.10294/) (2021)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model](https://mlsanity.com/paper/2302.00244/) (2023)
- [Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers](https://mlsanity.com/paper/2011.06069/) (2020)
- [The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights](https://mlsanity.com/paper/2203.02433/) (2022)

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

- [Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2503.01129/) (2025)
- [Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods](https://mlsanity.com/paper/2406.06954/) (2024)
- [Mixture-of-Experts Operator Transformer for Large-Scale PDE Pre-Training](https://mlsanity.com/paper/2510.25803/) (2025)
- [Distinguished Quantized Guidance for Diffusion-based Sequence Recommendation](https://mlsanity.com/paper/2501.17670/) (2025)
- [Machine Learning Insides OptVerse AI Solver: Design Principles and Applications](https://mlsanity.com/paper/2401.05960/) (2024)
- [SymMaP: Improving Computational Efficiency in Linear Solvers through Symbolic Preconditioning](https://mlsanity.com/paper/2510.24170/) (2025)
- [CoCo-MILP: Inter-Variable Contrastive and Intra-Constraint Competitive MILP Solution Prediction](https://mlsanity.com/paper/2511.09209/) (2025)
- [Accurate and Scalable Graph Neural Networks via Message Invariance](https://mlsanity.com/paper/2502.19693/) (2025)
- [On Efficiency-Effectiveness Trade-off of Diffusion-based Recommenders](https://mlsanity.com/paper/2510.17245/) (2025)
- [STNet: Spectral Transformation Network for Solving Operator Eigenvalue Problem](https://mlsanity.com/paper/2510.23986/) (2025)
- [RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains](https://mlsanity.com/paper/2511.02331/) (2025)
- [Evaluating the Robustness of Deep-Learning Algorithm-Selection Models by Evolving Adversarial Instances](https://mlsanity.com/paper/2406.16609/) (2024)

## Abstract (arXiv)

Machine learning has been successfully applied to improve the efficiency of Mixed-Integer Linear Programming (MILP) solvers. However, the learning-based solvers often suffer from severe performance degradation on unseen MILP instances -- especially on large-scale instances from a perturbed environment -- due to the limited diversity of training distributions. To tackle this problem, we propose a novel approach, which is called Adversarial Instance Augmentation and does not require to know the problem type for new instance generation, to promote data diversity for learning-based branching modules in the branch-and-bound (B&B) Solvers (AdaSolver). We use the bipartite graph representations for MILP instances and obtain various perturbed instances to regularize the solver by augmenting the graph structures with a learned augmentation policy. The major technical contribution of AdaSolver is that we formulate the non-differentiable instance augmentation as a contextual bandit problem and adversarially train the learning-based solver and augmentation policy, enabling efficient gradient-based training of the augmentation policy. To the best of our knowledge, AdaSolver is the first general and effective framework for understanding and improving the generalization of both imitation-learning-based (IL-based) and reinforcement-learning-based (RL-based) B&B solvers. Extensive experiments demonstrate that by producing various augmented instances, AdaSolver leads to a remarkable efficiency improvement across various distributions.