Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branching

Mixed Integer Linear Programming (MILP) is a fundamental NP-hard problem that has garnered significant attention from both academia and industry. The Branch-and-Bound (B&B) algorithm is the dominant approach for solving MILPs, where branching decisions play a critical role and have recently been enhanced by neural methods. However, these methods still struggle with semantic variation across depths, the scarcity of upstream nodes, and the costly collection of strong branching samples. To address these issues, we propose SC-MILP, a Dynamic Stratified Contrastive Training Framework for MILP Branching. Our method groups B&B nodes based on their feature distributions and learns depth-aware, fine-grained node representations through dynamic stratified contrastive training. To address data scarcity and imbalance at upstream nodes, we introduce an upstream-augmented MILP derivation procedure that generates both theoretically equivalent and perturbed instances. Experiments on both synthetic and real-world MILP benchmarks, including large-scale instances, show that SC-MILP significantly improves branching accuracy, reduces solving time, with particularly strong gains at upstream nodes.