Sharp Logarithmic Thresholds for Cut Schedules in an Abstract Branch-and-Cut Model

Abstract

Branch-and-cut interleaves branching with cutting-plane generation. How the two operations share the work of proving a bound is a basic theoretical question. We study an abstract model in which a tree certifies a target bound $Z$. Each branch node improves the bound by $\ell$ on one child and by $r$ on the other, where $0<\ell\le r$. The $i$th cut along a root-to-node path improves it by $c_i\ge0$, with cumulative improvement $C_k=\sum_{i=1}^k c_i$. Asymmetric branching enters through the rate $λ^{\star}>0$ defined by $e^{-λ^{\star}\ell}+e^{-λ^{\star}r}=1$. We establish uniform two-sided bounds of order $e^{λ^{\star}Z}$ on the minimal leaf count of pure branching trees. We then identify $\log k$ as the sharp threshold scale for the power of cutting. For cut schedules with extended limit $γ=\lim_{k\to\infty}C_k/\log k\in[0,\infty]$, minimal-size trees obey a trichotomy. If $γ=\infty$, cuts prove asymptotically all of the target. If $0\leγ<\infty$, the limiting fraction of the bound proved by cuts is $γλ^{\star}/(1+γλ^{\star})$. If $γ=0$, branch-and-cut has the same exponential size rate as pure branch-and-bound. This resolves open questions raised by Kazachkov, Le Bodic, and Sankaranarayanan on minimal-size trees under harmonically-worsening cuts, and generalizes their results to asymmetric branching and to all cut schedules in the model with this logarithmic limit. Finally, we show that branch-and-cut attains polynomial size in terms of $Z$ if and only if polynomially many cuts reduce the residual bound to $O(\log Z)$.

Disclosure

“with multiple variables, in the spirit of the multiple- and general-variable branching problems of Le Bodic and Nemhauser [18]. Acknowledgments. The author declares no competing interests. No data were generated or analyzed in this study. ChatGPT from OpenAI was used to refine the original proofs, and the author verified and takes full responsibility for the final draft. 12”

PDF page 12

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-24T00:34:12.480Z

Structural counts