Promoting Generalization for Exact Combinatorial Solvers via Adversarial Instance Augmentation.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• Machine learning accelerates Mixed-Integer Linear Programming (MILP) solvers.
• Learning-based solvers face performance degradation on unseen instances due to limited training data diversity.

Purpose of the Study:

• Propose Adversarial Instance Augmentation (AdaSolver) to enhance data diversity for MILP solvers.
• Improve the generalization capabilities of learning-based branch-and-bound (B&B) solvers.

Main Methods:

• AdaSolver augments MILP instance structures using an augmentation policy on bipartite graphs.
• Formulates the augmentation policy learning as a contextual bandit problem for adversarial training.
• Enables gradient-based adversarial training for both the solver and augmentation policy.

Main Results:

• AdaSolver achieves approximately 35% improvement in solving time across various distributions.
• Demonstrates significant sample efficiency gains, reducing solving time by 40% compared to GNN baselines with only 1% of training data.

Conclusions:

• AdaSolver is the first general framework to improve generalization for imitation-learning and reinforcement-learning-based B&B solvers.
• The method effectively addresses the data diversity challenge in learning-based MILP solvers.