verify_flow: Verify that a flow is optimal
In couplr: Optimal Pairing and Matching via Linear Assignment

verify_flow

R Documentation

Verify that a flow is optimal

Description

Checks a flow and a set of node potentials against the linear-programming optimality conditions for the minimum-cost flow problem, and returns the result of each check. Unlike the status field on a solve result, which records what the solver terminated on, this is a statement about the flow: certified_optimal is TRUE only when every condition holds. The comparisons are made within a relative tolerance, so what it establishes is optimality to that tolerance; the exact-arithmetic conclusion verify_assignment() can reach has no counterpart here, because the arc bounds and the potentials of a general flow are compared per arc against a tolerance that scales with them.

Usage

verify_flow(x, problem = NULL, potential = NULL, tol = 1e-09)

## S3 method for class 'flow_certificate'
print(x, ...)

Arguments

`x`	A `flow_certificate` object.
`problem`	The flow problem the flow belongs to: a `couplr_flow_problem` or a list with elements `n_nodes`, `supply` and `arcs`, where `arcs` is a data frame with columns `tail`, `head`, `lower`, `upper` and `cost` and node ids run from 1. Required unless `x` already carries one.
`potential`	Optional numeric vector of node potentials, one per node. Overrides any potentials on `x`.
`tol`	Relative tolerance for the feasibility and slackness comparisons. Each arc scales it by the largest of its cost and its two potentials, and the duality-gap comparison scales it by the magnitude of the objective, since a threshold below the resolution of the arithmetic that produced a number is not one a correct answer can meet.
`...`	Ignored.

Details

The problem is

  min  sum_a cost(a) f(a)
  s.t. (flow out of v) - (flow into v) = supply(v)   at every node v
       lower(a) <= f(a) <= upper(a)                  on every arc a

and, writing cbar(a) = cost(a) + pi(tail(a)) - pi(head(a)) for the reduced cost under the potentials pi, the conditions checked are primal feasibility, cbar(a) >= -tol(a) on every arc that can still take flow, and cbar(a) <= tol(a) on every arc carrying more than its lower bound. Their objective form is checked too: the duality gap is the sum of the slackness violations weighted by ⁠|cbar|⁠, so it is where a violation too small to trip the per-arc tolerance still accumulates.

tol is relative. Each arc is compared against

  tol(a) = tol * max(1, |cost(a)|, |pi(tail(a))|, |pi(head(a))|)

because cbar(a) is computed from those three numbers, and its last bits are worth the largest of them times the machine epsilon. A design that stacks lexicographic tier weights, as cardinality_match() does to rank cardinality above balance above distance, reaches potentials in the millions, where one unit in the last place is around 1e-9 and an exactly optimal flow cannot meet an absolute 1e-9. The scale never falls below 1, so a problem whose costs and potentials are of order 1 is checked against tol itself. The widest tolerance any comparison used is reported as dual_tolerance.

The check needs potentials. If x carries them, as a solve result does, they are used. Otherwise they are obtained by solving problem, which costs a second solve. Either way they are verified, not trusted: an arc priced below the tolerance makes the verification fail rather than pass.

Optimal potentials are shared by all optimal solutions of a linear program, so a flow from one solver can be certified against potentials from another.

Value

An object of class flow_certificate, a list with elements:

certified_optimal - logical, the conclusion. TRUE only when every condition below holds.
primal_feasible - logical; every arc inside its bounds and every node's net flow equal to its supply.
n_capacity_violations, n_conservation_violations, max_conservation_error - what primal feasibility failed on.
dual_feasible - logical; no arc that can still take flow prices below its own -tol(a).
complementary_slackness - logical; no arc above its lower bound prices above its own tol(a).
n_cs_violations, min_residual_reduced_cost, worst_arc - the smallest reduced cost over the residual graph and the arc attaining it, which is a violation when it falls below that arc's -tol(a). worst_arc is 0 when no arc can either take or give up flow.
dual_tolerance - the widest tol(a) any comparison was made against, so the verdict names the resolution it was reached at.
primal_objective, dual_objective, duality_gap - numeric.
tolerance - the relative tol as supplied.

Invisibly returns x.

Examples

# Two supply nodes shipping to two demand nodes, stated directly as a flow.
prob <- list(
  n_nodes = 4,
  supply  = c(2, 1, -2, -1),
  arcs = data.frame(
    tail  = c(1, 1, 2, 2),
    head  = c(3, 4, 3, 4),
    lower = c(0, 0, 0, 0),
    upper = c(2, 2, 2, 2),
    cost  = c(1, 3, 2, 1)
  )
)

# Both of node 1's units go to node 3, node 2's unit goes to node 4.
verify_flow(c(2, 0, 0, 1), prob, potential = c(0, 0, 1, 1))

# The same flow against potentials that certify nothing.
verify_flow(c(2, 0, 0, 1), prob, potential = c(0, 0, 0, 0))

couplr documentation built on Sept. 17, 2026, 1:08 a.m.