debajyotidasgupta/repro-branch-and-cut-bundle

Reproduction: Theoretical Challenges in Learning for Branch-and-Cut

Independent reproduction of ICML 2026 paper #17987 — Theoretical Challenges in Learning for Branch-and-Cut (Hongyu Cheng, Amitabh Basu; Johns Hopkins University). arXiv 2601.23249 · OpenReview gqKLmdooqZ.

Part of the Hugging Face × AlphaXiv ICML-2026 reproduction challenge.

What kind of reproduction this is

The paper is theoretical: every claim is a worst-case separation that predicts an exact branch-and-bound tree size for an explicitly constructed MILP family. There is no training and no dataset. We reproduce the claims exactly by

1. building each paper construction verbatim (polytopes, cut sets, objective coefficients), and
2. running them through a faithful, black-box branch-and-bound / branch-and-cut engine that implements the paper's standing assumptions (best-bound node selection, branching only on LP-fractional variables, strong-branching product score, incumbent bound pruning, total-node tree-size metric),

then checking that the measured integer node counts match the paper's closed-form formulas (2n+1, 2^(n+1)−1, 1+6(2^⌊m/9⌋−1), 2^(m+1)−1, 2^(k+1)·n/7).

Because the outputs are exact integers, the results are deterministic and hardware-independent — verified both locally and on an independent remote CPU.

Claims

Claim	Paper result	Reproduced
C1	LP-improvement cut selection ⇒ 2^Ω(n) larger SB tree than efficacy (Thm 3.1)	✅ C1=2m+1 (linear); C2 exponential, ratio ↑ with m
C2	ε RHS cut perturbation ⇒ min tree 1 vs 2^Ω(n) (Thm 3.3)	✅
C3	scores within ε of strong branching ⇒ 2^(n+1)−1 vs 2n+1 (Thm 4.1)	✅ SB=2n+1; π̂ contains full binary tree 2^(n+1)−1, gap=ε/2
C4	k deviations from SB ⇒ 2^Ω(k) blowup (Thm 4.4)	✅ tree ≈ 2^k × SB, ≥ 2^(k+1)·n/7
C5	identical scores, tie-break alone ⇒ exponential gap (Prop 4.2)	✅ π_min=2n+1; π_y=2^(n+1)−1

Plus the paper's supporting computations: Lemma 5.3 block LP values, the §5.1.1 two-variable cut-ranking example, and the Thm 3.1 per-cut LP-improvement / efficacy values — all reproduced exactly.

Layout

bnc/                 the reproduction toolkit (black-box over the LP)
  lp.py              LP relaxation solver (SciPy HiGHS)
  milp.py            MILP + root-cut representation
  bnb.py             branch-and-bound engine (best bound, node counting, depths)
  policies.py        strong branching, ε-perturbed, clipped, k-deviation, tie-break
  instances.py       every paper construction (Def 5.1, Thm 3.1/3.3, §5.1.1)
experiments/         lemma_checks.py + claim{1..5}_*.py + run_all.py
outputs/             JSON / CSV results + figures/ (interactive Plotly HTML)
make_figures.py      builds the figures from the CSVs
smoke_test.py        quick engine sanity checks

Reproduce

pip install -r requirements.txt
python smoke_test.py                       # engine sanity (Lemma 5.3, 2n+1 tree)
cd experiments && python run_all.py full   # all claims, exact tree sizes (~4 min, CPU)
cd .. && python make_figures.py            # interactive figures from the CSVs

run_all.py smoke runs a fast subset; run_all.py scaled pushes larger n/m.

Notes on faithfulness

• The engine never uses structural knowledge of the gadgets — it only solves LPs, counts fractional variables, and counts nodes. Matching the predicted tree sizes is therefore genuine evidence, not a re-statement of the proof.
• Strong branching is computed by actual LP look-ahead on both children of every candidate. Where the paper's exponential trees are produced by a fixed score-based rule (π̂, π_y, π̂_{n,k}), we run that rule directly and, at small n, verify by genuine strong-branching look-ahead that it makes the identical decisions and that its scores are within ε of strong branching (Claim 3) or identical (Claim 5).
• For the minimum-tree claims (C1's C2 tree, C2/Thm 3.3), we seed the optimal incumbent — allowed w.l.o.g. by the paper — so bound pruning is maximal and the exponential lower bounds are the strongest possible.