# Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branching

arXiv: https://arxiv.org/abs/2511.21107 · HTML: https://mlsanity.com/paper/2511.21107/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 45 references that are in the map.
- First posted on arXiv 26 Nov 2025.

## Builds on (most cited first, 16 of 16)

- [Supervised Contrastive Learning](https://mlsanity.com/paper/2004.11362/) (2020)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies](https://mlsanity.com/paper/2002.05120/) (2020)
- [MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers](https://mlsanity.com/paper/2205.14210/) (2022)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [Towards Foundation Models for Mixed Integer Linear Programming](https://mlsanity.com/paper/2410.08288/) (2024)
- [Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm](https://mlsanity.com/paper/2005.10026/) (2020)
- [Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories](https://mlsanity.com/paper/2205.14345/) (2022)
- [Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch](https://mlsanity.com/paper/2206.06965/) (2022)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2404.12638/) (2024)
- [MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation](https://mlsanity.com/paper/2311.02356/) (2023)
- [CAMBranch: Contrastive Learning with Augmented MILPs for Branching](https://mlsanity.com/paper/2402.03647/) (2024)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks](https://mlsanity.com/paper/2311.13843/) (2023)

## Built on by (most cited first, 1 of 1)

- [Reformulation-Contrastive Learning for Mixed Integer Programs](https://mlsanity.com/paper/2610.00730/) (2026)

## Abstract (arXiv)

Mixed Integer Linear Programming (MILP) is a fundamental class of NP-hard problems that has garnered significant attention from both academia and industry. The Branch-and-Bound (B&B) method is the dominant approach for solving MILPs and the branching plays an important role in B&B methods. Neural-based learning frameworks have recently been developed to enhance branching policies and the efficiency of solving MILPs. 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 ours, a Dynamic underlineStratified underlineContrastive Training Framework for underlineMILP Branching. It groups branch-and-bound nodes based on their feature distributions and trains a GCNN-based discriminative model to progressively separate nodes across groups, learning finer-grained node representations throughout the tree. 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. ours~effectively models subtle semantic differences between nodes, significantly enhancing branching accuracy and solving efficiency, particularly for upstream nodes. Extensive experiments on standard MILP benchmarks demonstrate that our method enhances branching accuracy, reduces solving time, and generalizes effectively to unseen instances.