Cutting Planes for Binarized Network Flow Problems

Andrea Lodi; Anton Derkach; Pierre Bonami; Sanjeeb Dash

arxiv: 2511.22838 · v2 · submitted 2025-11-28 · 🧮 math.OC

Cutting Planes for Binarized Network Flow Problems

Pierre Bonami , Sanjeeb Dash , Anton Derkach , Andrea Lodi This is my paper

Pith reviewed 2026-05-17 05:09 UTC · model grok-4.3

classification 🧮 math.OC MSC 90C11

keywords network flowbinarizationextended formulationcutting planesmixed-integer roundingMIP solversinteger programming

0 comments

The pith

Different ways to binarize bounded integers in network flow problems cause MIP solvers to generate different cutting planes and run at different speeds.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies integer programming problems that are network flows with bounded general-integer variables. It tests several extended formulations that replace each such variable with a linear combination of auxiliary binary variables plus linking constraints. Solvers show large performance differences across these formulations, and the authors trace the gaps to how effectively each formulation lets the solver produce cutting planes. They also highlight a family of mixed-integer rounding inequalities that gains special strength from the reformulations. The work supplies the first broad computational comparison and practical guidance on choosing binarizations for MIP solvers.

Core claim

For network flow problems with bounded general integers, different extended formulations that replace each integer variable by a sum of binaries connected by extra linear inequalities produce substantially different MIP solver performance. The performance variation is explained by the fact that each binarization changes the cutting planes the solver generates during branch-and-cut. A simple family of mixed-integer rounding inequalities is shown to be particularly effective under these reformulations and to improve solution times across several commercial and open-source MIP solvers.

What carries the argument

Extended formulations that replace each bounded general-integer variable with a linear combination of auxiliary binary variables plus additional linear constraints, and the way these formulations interact with cutting-plane generation routines inside MIP solvers.

If this is right

Choosing one binarization over another can materially change the effectiveness of the cuts a MIP solver produces on the same network flow model.
Mixed-integer rounding inequalities become stronger or more numerous under certain binarizations, leading to faster overall solution times.
The public data set allows direct comparison of cut statistics across formulations for any chosen solver.
Practical guidelines emerge for selecting binarization methods when network flow structure is present in an MIP.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same binarization effect on cut generation may occur in other structured integer programs that contain bounded general integers.
Solver developers could treat the choice of binarization as an explicit modeling parameter that is tuned for cut quality on a given problem class.
The released computational results make it possible to test whether specific families of cuts beyond mixed-integer rounding also benefit from particular binarizations.

Load-bearing premise

The runtime differences seen across binarizations are driven mainly by differences in the cutting planes the solver generates rather than by other unmeasured solver internals or by the particular test instances chosen.

What would settle it

Running the same network flow instances with cutting-plane generation turned off and still observing large runtime gaps between binarizations would indicate that the performance differences are not primarily due to cutting planes.

read the original abstract

We consider integer programming problems with bounded general-integer variables belonging to the general class of network flow problems. For those, we computationally investigate the effect on mixed-integer linear programming (MIP) solvers of the different ways of producing extended formulations that replace a bounded general integer variable by a linear combination of a set of auxiliary binary variables linked by additional linear constraints. We show that MILP solvers perform very differently depending on which extended formulations is used and we interpret that different performance through the lens of cutting planes generation. Finally, we discuss a simple family of mixed-integer rounding inequalities that especially benefit from the reformulation, and we show its benefit within different MIP solvers. This provides methodological and practical guidelines for the use of those extended formulations in MIP and, to the best of our knowledge, this is the first extensive computational analysis of the topic. All our data and tables are publicly available at https://github.com/anton-derkach1/binarizations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper delivers a useful empirical comparison of binarization choices for network-flow MIPs with public data, but the link from performance gaps to cutting-plane behavior rests on aggregate metrics rather than direct isolation.

read the letter

The main thing to know is that different ways of replacing bounded general integers with binaries in network flow MIPs produce clear differences in solver runtimes and node counts, and the authors tie those differences to how the formulations interact with cutting-plane routines, especially a family of mixed-integer rounding inequalities. They back this with a controlled set of experiments on public instances and release all data and tables on GitHub, which is a practical plus for anyone who wants to reproduce or build on the work. The comparison covers several extended formulations and shows that some binarizations let the MIR cuts tighten bounds more effectively inside standard solvers. That supplies concrete, if narrow, guidelines for modelers who face similar network structures. The experiments look reproducible and the test set is fixed rather than tuned to the claims, so circularity is not an issue. The soft spot is the causal story on cutting planes. The evidence is overall solve times and nodes explored across formulations; there are no reported counts of cuts generated, no root-node bound improvements broken out by cut type, and no ablations that disable cut generation to see how much of the gap remains. Other solver internals or instance quirks could share the credit, and the paper does not close that loop. The interpretation is still plausible given the problem class, but it stays one step short of direct verification. This work is aimed at MIP practitioners and researchers who routinely binarize general integers in network models and need to pick a formulation that plays well with existing solvers. A reader in that niche will get actionable advice and a starting point for further tests. It is coherent on its own terms and engages the relevant literature on extended formulations without overclaiming theory. It deserves a serious referee because the computational design is transparent and the data is public, even though revisions could usefully add cut statistics or disabled-cut runs to tighten the main interpretation.

Referee Report

2 major / 3 minor

Summary. The manuscript computationally investigates the impact of different binarization-based extended formulations for bounded general-integer variables within network flow problems on MILP solver performance. It reports that solvers exhibit substantially different runtimes and node counts depending on the chosen formulation, interprets these differences through the lens of cutting-plane generation (including mixed-integer rounding inequalities), and provides public data and tables at a GitHub repository. The study positions itself as the first extensive computational analysis of the topic and offers methodological guidelines for formulation choice in MIP.

Significance. If the performance differences and their attribution to cutting planes hold under closer scrutiny, the work supplies practical guidance for selecting binarizations in network-flow MIPs and highlights how extended formulations interact with modern solver cut generators. The public release of all data and tables is a clear strength that supports reproducibility and secondary analyses. The empirical nature of the claims means the significance is tied directly to the quality of the experimental design and the isolation of the proposed mechanism.

major comments (2)

[§4] §4 (Computational Experiments) and associated tables: aggregate runtimes and node counts are reported across binarizations, but no direct metrics (cut counts by type, root-node bound improvements from cuts, or ablation runs with cut generation disabled) are provided to isolate cutting-plane effects from presolve, branching, or heuristics. This leaves the central interpretive claim that performance differences arise primarily from cutting-plane generation unverified.
[§3.3 / §5] Discussion of MIR inequalities (likely §3.3 or §5): the manuscript introduces a family of mixed-integer rounding cuts that 'especially benefit from the reformulation' yet supplies neither an explicit derivation showing validity under each binarization nor separate computational results quantifying their isolated contribution versus the baseline solver cuts.

minor comments (3)

[Abstract / §1] The abstract and introduction could more precisely delimit the class of network-flow problems considered (e.g., which constraint structures are required for the binarization results to apply).
[§2] Notation for the auxiliary binary variables and linking constraints is introduced without a compact summary table; a single table collecting all binarization schemes would improve readability.
[§4] The GitHub repository link is given, but the manuscript does not state the exact solver versions, cut-generation settings, or random seeds used, which would aid exact reproduction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments and detailed review. We address each major comment point by point below, indicating the revisions we will incorporate.

read point-by-point responses

Referee: [§4] §4 (Computational Experiments) and associated tables: aggregate runtimes and node counts are reported across binarizations, but no direct metrics (cut counts by type, root-node bound improvements from cuts, or ablation runs with cut generation disabled) are provided to isolate cutting-plane effects from presolve, branching, or heuristics. This leaves the central interpretive claim that performance differences arise primarily from cutting-plane generation unverified.

Authors: We agree that direct metrics would strengthen the attribution of performance differences to cutting-plane generation. In the revised manuscript we will add tables reporting cut counts by type and root-node bound improvements extracted from solver logs for each binarization. Full ablation experiments with cut generation disabled are computationally expensive and were not performed in the original study; we will instead discuss this limitation and support the interpretation using the available performance data together with known solver cut-generation behavior on extended formulations. revision: partial
Referee: [§3.3 / §5] Discussion of MIR inequalities (likely §3.3 or §5): the manuscript introduces a family of mixed-integer rounding cuts that 'especially benefit from the reformulation' yet supplies neither an explicit derivation showing validity under each binarization nor separate computational results quantifying their isolated contribution versus the baseline solver cuts.

Authors: We will include an explicit derivation of the validity of the mixed-integer rounding inequalities for each binarization in the revised Section 3.3. We will also add separate computational results or an ablation-style analysis that isolates the contribution of these inequalities relative to the solver's default cuts. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical comparison of solver performance on fixed test sets

full rationale

The paper performs a computational study of MILP solver behavior on network-flow instances under different binarized extended formulations. Performance metrics (runtimes, nodes) are obtained directly from external solver runs on a public test set; no parameter is fitted to a data subset and then re-used as a 'prediction,' and no derivation reduces to a self-citation chain or self-defined quantity. The discussion of MIR inequalities is presented as a standard family that benefits from the reformulations, without claiming a first-principles derivation that collapses to the inputs. The study is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard MIP theory (branch-and-cut, mixed-integer rounding) and on computational testing rather than new free parameters, invented entities, or ad-hoc axioms.

axioms (1)

standard math Commercial and open-source MIP solvers implement branch-and-cut with standard cutting-plane separators.
Invoked when the authors attribute performance differences to cutting-plane generation inside the solvers.

pith-pipeline@v0.9.0 · 5462 in / 1270 out tokens · 45572 ms · 2026-05-17T05:09:05.711783+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We show that MILP solvers perform very differently depending on which extended formulation is used and we interpret that different performance through the lens of cutting planes generation.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

, " * write output.state after.block = add.period write newline

ENTRY address author booktitle chapter doi edition editor eid howpublished institution isbn issn journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1...

work page
[2]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in "" FUNCTION format.date year ...

work page

[1] [1]

, " * write output.state after.block = add.period write newline

ENTRY address author booktitle chapter doi edition editor eid howpublished institution isbn issn journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1...

work page

[2] [2]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in "" FUNCTION format.date year ...

work page