{"ID":6023610,"CreatedAt":"2026-07-08T01:00:23.257252134Z","UpdatedAt":"2026-07-10T14:27:52.484755835Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06343","arxiv_id":"2607.06343","title":"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\u003c\\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}\u003e0$ 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γ\u003c\\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)$.","short_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...","url_abs":"https://arxiv.org/abs/2607.06343","url_pdf":"https://arxiv.org/pdf/2607.06343v1","authors":"[\"Hongyi Jiang\"]","published":"2026-07-07T14:40:09Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}