[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}
}