MIRAGE: Duality-Inspired MILP Augmentation for Representation Learning

Learning high-quality representations of mixed-integer linear programming (MILP) is crucial for advancing machine learning (ML)-based methods, yet remains challenging due to the discrete nature of MILPs and their extreme sensitivity to small perturbations. Although contrastive learning has proven highly effective for representation learning in domains such as computer vision, designing effective data augmentations for MILPs is particularly difficult. To address this challenge, we propose MIRAGE, a principled data augmentation framework grounded in the invariance of the piecewise-affine dual price function induced by the branch-and-bound (B&B) algorithm. Viewing this dual function as a recorded, solver-level surrogate of the MILP's lower-bound structure, we derive two complementary augmentation certificates that act as its right-hand and objective-side projections. Both certificates are provably invariant under the same dual price function on the recorded B&B tree, and therefore preserve either the structural similarity of the search tree or the optimality of the original optimal solution. Empirically, we integrate MIRAGE with ML models for two significant downstream tasks—learning to branch and predict-and-search—and observe consistent performance improvements across multiple benchmarks. By grounding MILP data augmentation in a single, solver-induced duality quantity, our work provides a principled and effective approach to MILP representation learning.