Promoting Generalization for Exact Combinatorial Solvers via Adversarial Instance Augmentation

Machine learning has been successfully applied to accelerate Mixed-Integer Linear Programming (MILP) solvers. However, the learning-based solvers often suffer from severe performance degradation on unseen MILP instances due to the limited number of training instances and diversity of training distributions. To tackle this problem, we propose a novel data augmentation approach, called Adversarial Instance Augmentation, to promote the data diversity for learning-based branching modules in branch-and-bound (B&B) Solvers (AdaSolver). To generate diverse augmented instances, AdaSolver uses an augmentation policy to augment the structures of the bipartite graphs representing MILP instances. The major technical contribution is that AdaSolver formulates the non-differentiable learning problem of the augmentation policy as a contextual bandit problem, enabling efficient gradient-based adversarial training for the learning-based solver and 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 and reinforcement-learning-based B&B solvers. Experiments demonstrate that AdaSolver leads to a remarkable roughly 35% improvement in solving time over the B&B solver across various distributions. Moreover, AdaSolver significantly improves the sample efficiency by roughly 40% reduction in solving time compared to the competitive GNN branching baseline with only 1% of the training instances.