Research map / Label-efficient and robust learning / Recognition and long-tail
CAMBranch: Contrastive Learning with Augmented MILPs for Branching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CAMBranch, which augments MILPs via variable shifting to create labeled expert samples for Strong Branching imitation, and uses contrastive learning between MILPs and augmented MILPs, reaching competitive branching performance with only 10% of expert data.
Problem
Imitation learning for neural branching in branch-and-bound requires collecting very many Strong Branching expert samples, which is extremely time-consuming for MILP solving.
Approach
Generate Augmented MILPs by shifting variables of existing MILPs; prove that Strong Branching decisions are preserved under the shift, so augmented instances come with free expert labels; pair each MILP with its augmented counterpart as positives in an infoNCE contrastive loss on GCNN graph embeddings, plus a consistency loss on variable probabilities.
Key results
- On hard Capacitated Facility Location, CAMBranch (10%) solves in 496.86 s vs 1020.58 s for GCNN in the Table 2 reported results (Easy/Medium/Hard trained on Easy), and wins 33/40 hard instances.
- On Set Covering hard, CAMBranch (10%) achieves 131.79 s and 42/100 wins, beating GCNN (158.81 s, 19/94).
- Data collection for 100k samples on Capacitated Facility Location takes 84.79 h, whereas CAMBranch's pipeline takes 8.76 h, an 89.67% time saving.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| train CAMBranch (10%) instead of GCNN (10%) | branching policy · Combinatorial Auction Hard | solving time (s): 672.88 -> 470.83 | Helped |
| train CAMBranch (10%) instead of GCNN (10%) | branching policy · Capacitated Facility Location Hard | solving time (s): 695.96 -> 496.86 | Helped |
| train CAMBranch (10%) instead of GCNN (10%) | branching policy · Set Covering Hard | solving time (s): 144.40 -> 131.79 | Helped |
| add contrastive learning (ablation) | CAMBranch (10%) · Set Covering | acc@1: 64.75 ± 1.43 -> 65.27 ± 3.92 | No clear effect |
| add contrastive learning (ablation) | CAMBranch (10%) · Set Covering Easy | solving time (s): 6.55 -> 6.79 | Hurt |
| add contrastive learning (ablation) | CAMBranch (10%) · Set Covering Medium | solving time (s): 66.09 -> 61.00 | Helped |
| add contrastive learning (ablation) | CAMBranch (10%) · Set Covering Hard | solving time (s): 1472.84 -> 1427.02 | Helped |
| increase training sample ratio from 10% to 20% (ablation) | CAMBranch · Combinatorial Auction Hard | solving time (s): 131.79 -> 103.38 | Helped |
| increase training sample ratio from 10% to 20% (ablation) | CAMBranch · Maximum Independent Set Hard | solving time (s): 496.86 -> 416.24 | Helped |
Surprising findings
- On Set Covering, CAMBranch (10%) has lower imitation accuracy than GCNN (10%) at acc@1 variance-level differences, and it wins fewer Easy instances (12/100) than GCNN (10%) (44/100).
Limitations
- Augmented samples still require Strong Branching labels on the original MILPs, so expert collection is reduced but not eliminated.
- CAMBranch trails GCNN trained on full data in imitation accuracy, notably on Set Covering.
- Results vary across seeds and sample ratios; some metrics favor GCNN (10%) or RPB.
Experimental setup
Datasets: Set Covering instances Combinatorial Auction instances Capacitated Facility Location instances Maximum Independent Set instances Strong Branching expert samples collected via SCIP 6.0.1
Benchmarks: Set Covering Combinatorial Auction Capacitated Facility Location Maximum Independent Set
Metrics: solving time (SGM) number of B&B nodes number of wins imitation accuracy acc@1/5/10
Baselines: RPB FSB GCNN GCNN (10%)
Builds on: GCNN bipartite branching (Gasse et al.) infoNCE Strong Branching
Closest papers by meaning
- Generative Branching for Mixed-Integer Linear Programming (AAAI 2026 · similarity 0.92)
- SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch (AAAI 2025 · similarity 0.86)
- Contrastive Predict-and-Search for Mixed Integer Linear Programs (ICML 2024 · similarity 0.85)
- Rethinking the Capacity of Graph Neural Networks for Branching Strategy (NeurIPS 2024 · similarity 0.85)
- Towards Foundation Models for Mixed Integer Linear Programming (ICLR 2025 · similarity 0.85)
- ACM-MILP: Adaptive Constraint Modification via Grouping and Selection for Hardness-Preserving MILP Instance Generation (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.