[Model] MinimumCostMaximumFlow

[zhangjieqingithub]

Motivation

The catalog has several flow-like models, but it does not have the continuous minimum-cost maximum-flow formulation used by CellRouter.

This model is useful because it records the CellRouter-aligned optimization target directly:

• first maximize the amount of flow sent from a designated source to a designated sink,
• then, among maximum-value flows, minimize total arc cost,
• keep the native continuous flow domain rather than imposing integrality.

This avoids the ambiguity of the broader name MinimumCostFlow, which often means a fixed-demand or arbitrary-supply formulation.

Associated rule:

• [Rule] MinimumCostMaximumFlow to MinimumCostCirculation #1031

Definition

Name: MinimumCostMaximumFlow
Reference:

• Aviv Regev et al. / CellRouter paper: L. Lummertz da Rocha et al., "Reconstructing complex single-cell trajectories using CellRouter," Nature Communications 9, 892, 2018. https://doi.org/10.1038/s41467-018-03214-y
• Standard min-cost-flow equivalence reference: MIT 6.854 notes, "Min-cost flow algorithms." https://courses.csail.mit.edu/6.854/21/Scribe/s10-minCostFlowAlg/s10-minCostFlowAlg.html

Let G = (V,E) be a finite directed multigraph with loops and parallel arcs allowed. The instance has:

• a designated source vertex s in V,
• a designated sink vertex t in V, with s != t,
• finite arc capacities u_e >= 0,
• nonnegative arc costs c_e >= 0.

A feasible flow is a function
f : E -> R_{>= 0}
such that:

• 0 <= f_e <= u_e for every arc e,
• for every vertex v notin {s,t}, total inflow at v equals total outflow from v.

The value of a flow is the net outflow from the source:
|f| = sum_{e in delta^+(s)} f_e - sum_{e in delta^-(s)} f_e.

The cost of a flow is:
cost(f) = sum_{e in E} c_e f_e.

The objective is lexicographic:

1. maximize |f|,
2. subject to maximum flow value, minimize cost(f).

So this is an optimization problem with a lexicographic objective.

Variables

Let m = |E|.

• Count: m continuous variables
• Per-variable domain: R_{>= 0}
• Meaning: variable f_e is the amount of flow sent on arc e

A configuration is feasible iff it satisfies all capacity constraints and all nonterminal flow-conservation constraints.

Schema (data type)

Type name: MinimumCostMaximumFlow

Paper-aligned variant:

• directed multigraph input,
• continuous nonnegative real flows,
• finite nonnegative real capacities,
• finite nonnegative real costs.

Field	Mathematical type	Description
graph	finite directed multigraph	Directed network; loops and parallel arcs allowed
source	vertex	Source vertex s
sink	vertex	Sink vertex t
capacities	E -> R_{>=0}	Finite arc capacity function u
costs	E -> R_{>=0}	Nonnegative arc cost function c

The cleaned model should not include a fixed required flow value. Multiple biological source and target sets are best treated as an instance-construction layer that adds auxiliary source and sink nodes before producing this final single-source/single-sink network.

Complexity

This problem is polynomial-time solvable. A safe registry-level complexity for a first implementation is to use the generic linear-programming formulation, with num_arcs flow variables and O(num_vertices + num_arcs) linear constraints.

A conservative exact expression for the catalog can therefore be:
poly(num_vertices + num_arcs)

If the registry requires a concrete expression string, use a deliberately conservative polynomial placeholder such as:
(num_vertices + num_arcs)^6

This is not intended as a best-known bound. It is a conservative polynomial bound justified by the standard linear-programming formulation of min-cost flow. A sharper strongly-polynomial network-flow bound can be substituted during implementation if the implementer chooses a specific algorithm and citation.

Reference for polynomial-time linear programming:

• L. G. Khachiyan, "A polynomial algorithm in linear programming," Soviet Mathematics Doklady 20, 191-194, 1979.

Extra Remark

For the CellRouter-aligned model:

• flows are continuous, not integral,
• capacities are finite nonnegative reals,
• costs are nonnegative because the biological construction uses costs of the form -log(c_ij) from similarity/capacity scores,
• the objective is lexicographic max-flow-then-min-cost, not fixed-demand min-cost flow.

Integral-flow and fixed-demand variants are useful generalizations, but they should not be the default model for the CellRouter paper.

Reduction Rule Crossref

• [Rule] MinimumCostMaximumFlow to MinimumCostCirculation #1031

How to solve

• It can be solved by a polynomial-time min-cost max-flow algorithm.
• It can be reduced to MinimumCostCirculation via [Rule] MinimumCostMaximumFlow to MinimumCostCirculation #1031.
• It can also be expressed as a two-stage linear program: first maximize flow value, then minimize cost with that value fixed.

Example Instance

Take vertices {s, a, b, t} and arcs:

Arc	Capacity	Cost
s -> a	2	1
s -> b	1	0
a -> b	1	0
a -> t	1	1
b -> t	2	2

Expected Outcome

The maximum possible s-t flow value is 3.

One optimal minimum-cost maximum flow is:

• f(s,a) = 2
• f(s,b) = 1
• f(a,b) = 1
• f(a,t) = 1
• f(b,t) = 2

Flow conservation holds at a and b:

• vertex a: inflow 2, outflow 1 + 1 = 2,
• vertex b: inflow 1 + 1 = 2, outflow 2.

The value is 3, and the cost is:
2*1 + 1*0 + 1*0 + 1*1 + 2*2 = 7.

A value-2 flow using only paths through b can be cheaper, but it is not optimal because the primary objective is maximum flow value. This example therefore checks the lexicographic objective rather than a simple minimum-cost objective.

BibTeX

@article{CellRouter2018,
  title   = {Reconstructing complex single-cell trajectories using CellRouter},
  journal = {Nature Communications},
  volume  = {9},
  pages   = {892},
  year    = {2018},
  doi     = {10.1038/s41467-018-03214-y},
  url     = {https://doi.org/10.1038/s41467-018-03214-y}
}

@article{Khachiyan1979LP,
  author  = {L. G. Khachiyan},
  title   = {A polynomial algorithm in linear programming},
  journal = {Soviet Mathematics Doklady},
  volume  = {20},
  pages   = {191--194},
  year    = {1979}
}

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	Pass	Novel problem; not in catalog; planned reduction to MinimumCostCirculation via #1031; distinct from existing MinimumEdgeCostFlow
Non-trivial	Pass	Continuous lexicographic max-flow-then-min-cost is distinct from any existing flow model (MinimumEdgeCostFlow, DirectedTwoCommodityIntegralFlow, IntegralFlow*, PathConstrainedNetworkFlow, etc.)
Correctness	Pass (with recommendation)	Definition is well-formed. Complexity correctly identified as polynomial-time (no spurious NP-hardness/exponential claim). Cited references (CellRouter, MIT 6.854 notes, Khachiyan 1979) all resolve.
Well-written	Warn	Schema uses mathematical types rather than concrete data types; the lone maximum-value flow in the example is unique, so the example does not separately exercise the min-cost tiebreaker among multiple max-flows.

Overall: 3 passed, 1 warning, 0 failures

---

Usefulness

• pred show MinimumCostMaximumFlow returns "Unknown problem" — not currently in the catalog.
• The Reduction Rule Crossref section links a planned [Rule] issue [Rule] MinimumCostMaximumFlow to MinimumCostCirculation #1031 (MinimumCostMaximumFlow to MinimumCostCirculation); the companion target model is proposed in [Model] MinimumCostCirculation #1030. So the node will not be an orphan.
• Differentiates cleanly from the existing MinimumEdgeCostFlow, which minimizes the number of arcs carrying nonzero flow (weighted by price), uses integral capacities, and requires a fixed flow value R. The proposed model is continuous, lexicographic (max-flow then min-cost), and has no fixed-demand parameter.
• Motivation is concrete (CellRouter / single-cell trajectory reconstruction). Solver path is identified (poly-time MCMF, plus a planned reduction to MinimumCostCirculation, plus a two-stage LP formulation). No direct ILP claim is made, so no <Model> to ILP companion [Rule] issue is required.

Non-trivial

Checked against pred list (190 problem types, 260 reductions). Other flow models in the catalog: MinimumEdgeCostFlow, DirectedTwoCommodityIntegralFlow, IntegralFlowBundles, IntegralFlowHomologousArcs, IntegralFlowWithMultipliers, PathConstrainedNetworkFlow, UndirectedFlowLowerBounds, UndirectedTwoCommodityIntegralFlow. None of them use a lexicographic (max-flow-then-min-cost) objective over a continuous flow domain on a single-commodity, single-source/single-sink directed multigraph. Genuinely distinct feasibility-objective pair.

Correctness

Complexity claim — sanity-checked for the polynomial-time class. The issue correctly declares this as polynomial-time and cites Khachiyan's polynomial algorithm for linear programming (Khachiyan, Soviet Math. Doklady 20, 1979). This is consistent with the standard textbook result — min-cost max-flow with integer or rational capacities and costs is polynomial-time via LP, and strongly polynomial via combinatorial methods (e.g., Tardos 1985; Orlin 1993). No NP-hardness or purely exponential bound is claimed. Good.

Citation verification:

Reference	Status
L. Lummertz da Rocha et al., "CellRouter," Nat. Commun. 9, 892, 2018, DOI 10.1038/s41467-018-03214-y	DOI resolves; paper title on the publisher page is "Reconstruction of complex single-cell trajectories using CellRouter" (issue says "Reconstructing" — minor wording slip, not material)
MIT 6.854/21 scribe notes "Min-cost flow algorithms," s10	URL resolves to the published lecture notes
Khachiyan 1979, "A polynomial algorithm in linear programming," Soviet Math. Doklady 20:191-194	Well-known foundational LP paper

Recommendations

• Sharpen the concrete complexity expression. The placeholder (num_vertices + num_arcs)^6 is openly described as a conservative LP-based stand-in, but no algorithm has exactly this exponent — it makes the catalog row read worse than what is known. A more defensible strongly-polynomial bound is Orlin's enhanced capacity scaling, O((num_arcs * log(num_vertices)) * (num_arcs + num_vertices * log(num_vertices))) (Orlin, Operations Research 41:338-350, 1993). It can be added later during implementation, as the issue already anticipates.
• Fix the cited title from "Reconstructing" to "Reconstruction" to match the published paper.

Well-written

• All template sections present and substantive (Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance, Expected Outcome, Reduction Rule Crossref).
• Definition is formal and precise: quantifiers explicit ("for every arc", "for every vertex notin {s,t}"), feasibility conditions and objective clearly separated, lexicographic order spelled out.
• Symbols defined before first use (G = (V,E), s, t, u_e, c_e, m = |E|).
• Schema is borderline. It enumerates fields in mathematical language (finite directed multigraph, E -> R_{>=0}) rather than concrete data types (e.g., DirectedGraph, Vec<f64>, usize), unlike the existing MinimumEdgeCostFlow schema (DirectedGraph, Vec<i64>, usize). Implementers will likely need to lower these to concrete types anyway. Warn: consider listing the concrete intended Rust types in the field table to match existing models in the catalog.
• Example instance: 4 vertices, 5 arcs, multiple flow values feasible. Worked-out conservation, value, and cost all check out arithmetically:
  • Conservation at a: in=2, out=1+1=2 ✓
  • Conservation at b: in=1+1=2, out=2 ✓
  • Cost = 2*1 + 1*0 + 1*0 + 1*1 + 2*2 = 7 ✓
• However: with capacities cap(s,a)=2, cap(s,b)=1, both source arcs must be saturated in any max-flow (cut {s} has capacity 3). With cap(a,t)=1, the surplus 1 at a must route via a->b, and b->t must carry the resulting 2. So the displayed value-3 flow is the only max-flow on this instance. The example therefore exercises the "max-flow priority over min-cost" tiebreaker correctly (any value-2 flow is dominated), but it does not exercise the secondary "min-cost among multiple max-flows" tiebreaker, because there is only one max-flow. Warn: add an alternative example (or extend this one with a parallel arc, e.g., a second s->a arc, or an extra cheaper s->b route at cost 0) so that at least two distinct value-3 flows exist with different costs. That way a round-trip closed-loop test can catch implementations that pick a maximum-value flow but ignore the cost tiebreaker.

Recommendations Summary

• Tighten complexity expression to a defensible strongly-polynomial bound (e.g., Orlin 1993).
• Fix paper title ("Reconstruction" not "Reconstructing").
• Convert schema field type_names to concrete data types matching other flow-model entries.
• Extend the example so the min-cost tiebreaker is genuinely tested.

[isPANN]

/review-structural — commit 03101cc (post-impl, code-quality + bug sweep)

Verdict: pass — Model is correctly implemented, faithfully matches the issue's lex (max-value, min-cost) objective via a sound scalarization; small documentation/comment nits only, no blockers.

Issue compliance

• Mathematical definition matches issue: yes. The lex objective (max |f|, min cost(f)) is encoded as score = M*(B − |f|) + cost(f) with M = Σ c(a)*cost(a) + 1 > any feasible cost and B = Σ c(a) ≥ |f|, so a single Min<i64> strictly orders by max-value first, min-cost on ties. Module doc explicitly flags the integral-flow restriction (matching the MECF precedent) and notes that integrality of caps + costs preserves the optimum.
• Schema fields match: yes. graph: DirectedGraph, source: usize, sink: usize, capacities: Vec<i64>, costs: Vec<i64>. Field names line up with the constructor and the canonical example. CLI flags wired via flag_map() (graph→--arcs, plus --source/--sink/--capacities/--costs), and example_for("MinimumCostMaximumFlow") is registered.
• Canonical example: ok. The diamond instance (V=4, 5 arcs, caps [2,1,1,1,2], costs [1,0,0,1,2], s=0, t=3) yields the optimum f=[2,1,1,1,2] with |f|=3, cost=7, and the dedicated test_minimum_cost_maximum_flow_lex_tiebreaker test on a separate 5-vertex bottleneck instance actually exercises the lex tiebreaker (two value-1 flows with costs 1 vs 5, brute force must pick cost 1). This directly addresses the check-issue note that the original example admits only a unique max-value flow. dims = [3,2,2,2,3] (72 configs) and the tiebreaker dims [2,2,2,2,2] (32 configs) keep brute force well under the 5s test budget.

Findings

• Blockers (correctness): none. Verified by manual trace:
  • flow_value correctly nets outflow − inflow at source, handles self-loops by adding then subtracting (zero net).
  • is_feasible checks config length, per-arc capacity, and per-vertex conservation at non-terminals; matches the math in the issue.
  • evaluate returns Min(None) for any infeasibility (capacity, conservation, or wrong-length config), exercised by 3 dedicated tests.
  • Lex scalarization is provably correct: since M > max feasible cost, score(f1) < score(f2) iff (B−|f1|, cost(f1)) <_lex (B−|f2|, cost(f2)).
  • 9 tests in src/unit_tests/models/graph/minimum_cost_maximum_flow.rs cover creation, optimal evaluate, suboptimal evaluate, two infeasibility modes, wrong-length config, brute-force solver on the canonical instance, the lex tiebreaker, and serialization roundtrip — well above the structural threshold of 3.
• Nits (quality/HCI):
  • The canonical-example comment in canonical_model_example_specs() (src/models/graph/minimum_cost_maximum_flow.rs:320-323) is misleading: "send 2 units via 0→1→3 (cost 21 + 21 = 4)" is impossible because arc (1,3) has capacity 1. The optimum actually routes 2 units on (0,1), splits 1 unit each on (1,2) and (1,3) at vertex 1, and merges them at vertex 3. The final config [2,1,1,1,2] and cost 7 are right; only the route-description comment is incorrect.
  • The lex-tiebreaker test comment (test file, lines 148-149) says "Path via 1 has cost 1+0=1; path via 2 has cost 5+0=5", which conflates arc-index numbering and vertex numbering. It should say "path via vertex 2" vs "path via vertex 3" (or equivalently "via arc 1" vs "via arc 2"). The assertions on flow_value, total_cost, and the explicit witness [1,1,0,1,0] are all correct.
  • Schema description field for capacities and costs says "non-negative" but the type is Vec<i64> (signed). Constructor enforces non-negativity via assert!. Could be slightly clearer to call out the assertion in the field description, but the current wording is acceptable and consistent with MinimumEdgeCostFlow.
  • The registered complexity (num_vertices + num_arcs)^6 is described in both the paper and the module as a "conservative polynomial placeholder". This matches the issue's explicit guidance and is acceptable; if someone wants to tighten it later, Orlin 1993 gives strongly-polynomial bounds.
  • Display name in the paper is "Minimum-Cost Maximum-Flow" with a hyphen; module doc and code use the same hyphenated form. Internally consistent.