Air-Branching: Learning to branch via adversarial inverse reinforcement learning in mixed-integer linear programming

Counts differ because each database indexes a different set of publications. We treat OpenAlex as the canonical count; Google Scholar is not shown (no API, and crawling it violates its ToS).

Mixed-Integer linear programming (MILP) problems are typically solved using the branch-and-bound method, with branching variable selection (BVS) rules significantly influencing solution efficiency. Recent studies have increasingly emphasized the application of Imitation Learning (IL) and Reinforcement Learning (RL) in the development of BVS policies. However, IL methods are often constrained by the extensive data requirements and the inherent difficulty of matching or exceeding expert-level performance. Likewise, RL methods encounter notable challenges, particularly the complexity arising from long episodes and the issue of sparse reward signals. We address these challenges by introducing Air-Branching, a novel approach leveraging adversarial inverse reinforcement learning (IRL) to learn dense reward structures from limited expert data. Specifically, our approach employs warm-up training for the expert reward function to accelerate the convergence of early-stage policy training, addressing the long-episode problem. We also utilize a hybrid mechanism that integrates both expert and original rewards, enabling the branching policy to potentially surpass the strong branching expert. The experimental results show that Air-Branching outperforms the IL method (with the same amount of data) and all baseline RL methods, while its solving efficiency surpasses the state-of-the-art open-source solver SCIP. Moreover, in a real-world benchmark and some cases of standard benchmarks, Air-Branching’s solving efficiency exceeds that of the IL method trained with 10 times the data volume.