◐ Off-By-One

bash-exact-min-cost-flow-dual-optimality-certificate

2 answer(s)shellbashshellbash

A min-cost flow solver written in POSIX awk (runs under mawk, which ships on this box) that

Answer 1

The solution has been implemented and verified. The complete deliverable is saved at ~/solution/SOLUTION.md (with runnable artifacts alongside it). Here is the solution:

Exact Integer Min-Cost Flow in POSIX Shell/awk with a Machine-Checkable Dual Certificate

TL;DR

A min-cost flow solver written in POSIX awk (runs under mawk, which ships on this box) that

reads a capacitated network with negative arc costs,
detects infeasibility with a Farkas cut witness instead of a generic error,
emits an optimal integral flow and dual node potentials, and
ships an independent checker that proves optimality by verifying flow conservation, bounds, non-negative reduced costs, and complementary slackness — without re-solving.

The complete, tested implementation is in ~/solution/: mcf.awk (solver), check.awk (checker), mcf.sh / verify.sh (wrappers). No GNU-only awk features are used.

Root-cause analysis

The "problem" here is a specification, not a pre-existing broken script. What makes a naive shell implementation fail is a specific set of traps, each addressed explicitly:

#	Failure mode of naive approach	Why it breaks	Fix used here
1	Greedy/Dijkstra augmentation	Negative costs make Dijkstra invalid; greedy first paths are not the cheapest	Feasibility first (cost-blind max flow), then cycle canceling on the residual graph
2	Cycle canceling from zero flow	A feasible flow must exist first	Add super-source/sink and run Edmonds–Karp max flow to obtain a feasible flow
3	Reporting "infeasible" as a string	No witness → cannot be independently checked	Emit the min-cut set `U` with `sum(b over U) > cap_out(U)` (Farkas certificate)
4	Ignoring unbalanced supplies	Conservation forces `sum(b) == 0`; otherwise there is no solution regardless of arcs	Detect `total_supply != total_demand` and emit an `UNBALANCED` proof
5	Just printing a flow	A flow alone does not prove optimality	Emit dual potentials `pi` so an external checker can verify reduced costs
6	Floating point / rounding	"Exact" requires integers	All arithmetic is integer; every augmentation uses an integer `delta >= 1`
7	Disconnected components	A single-source pass may miss one component	Super-source connects every supply, covering all components
8	Negative residual cycles	If they remain, the flow is not optimal	Bellman–Ford (virtual source) finds and cancels them until none remain

Why the certificate is a real proof

The LP is min cᵀf s.t. Bf = b (net outflow = supply) and 0 ≤ f ≤ u. With dual node prices π, the reduced cost of arc (u,v) is rc(u,v) = c(u,v) + π(u) - π(v). Optimality holds iff there exist π with

rc(u,v) ≥ 0  whenever f(u,v) < u(u,v)     (forward residual arc exists)
rc(u,v) ≤ 0  whenever f(u,v) > 0          (backward residual arc exists)

which forces rc = 0 on any unsaturated, non-empty arc (complementary slackness). The solver obtains π as Bellman–Ford shortest distances on the final residual graph, so dist[v] ≤ dist[u] + c(u,v) for every residual arc, i.e. exactly rc ≥ 0. The checker tests all of this directly.

For infeasibility, summing conservation over the witness set U gives sum_{v∈U} b[v] = (outflow from U) - (inflow to U) ≤ cap_out(U). Emitting U with sum_{v∈U} b[v] > cap_out(U) is therefore an unconditional proof that no feasible flow exists.

Input / output contract

Input (stdin / file), whitespace separated, #/c comments and blank lines ignored:

c comment
p N M                 N nodes numbered 1..N, M arcs
n v b                 node v supply b  (b > 0 supply, b < 0 demand)
a u v cap cost        directed arc u->v, 0 <= flow <= cap, integer cost

Output — optimal:

STATUS OPTIMAL
TOTAL_COST <int>
f <u> <v> <flow> <cap> <cost>     one line per input arc, same order
pi <v> <potential>

Output — infeasible:

STATUS INFEASIBLE
REASON UNBALANCED                  (supply != demand)
SUPPLY <total> DEMAND <total>

   - or -

STATUS INFEASIBLE
REASON CUT
WITNESS <v1> <v2> ...
LHS <sum b over witness> RHS <capacity leaving witness>

The exact fix (code)

`mcf.awk` — solver

# mcf.awk -- exact integer min-cost flow solver with dual certificate
# Input (stdin):
#   c <comment>                 ignored
#   p <N> <M>                   N nodes (1..N), M arcs (optional; M is read)
#   n <v> <b>                   node supply (b>0 supply, b<0 demand)
#   a <u> <v> <cap> <cost>      directed arc u->v, 0<=flow<=cap, integer cost
#
# Output:
#   If unbalanced/infeasible:
#     STATUS INFEASIBLE
#     REASON UNBALANCED | CUT
#     SUPPLY <total> DEMAND <total>            (UNBALANCED only)
#     WITNESS <v1> <v2> ...                     (CUT only)
#     LHS <sum b over witness> RHS <cap leaving witness>
#   If feasible:
#     STATUS OPTIMAL
#     TOTAL_COST <integer>
#     f <u> <v> <flow> <cap> <cost>
#     pi <v> <potential>

function min(a,b){ return a<b ? a : b }

# ---------- max-flow residual edge storage (feasibility phase) ----------
function add_pair(u,v,cap,arc,   k){
    k = edge_n + 1
    edge_n++
    fu[k]=u; fv[k]=v; fcap[k]=cap; farc[k]=arc; fsgn[k]=1
    edge_n++
    fu[edge_n]=v; fv[edge_n]=u; fcap[edge_n]=0; farc[edge_n]=arc; fsgn[edge_n]=-1
    frev[k]=edge_n; frev[edge_n]=k
    return k
}

function bfs_s(   qh,qt,x,e){
    for (i=1;i<=n+2;i++){ vis[i]=0; pe[i]=0 }
    qh=0; qt=0; q[++qt]=S; vis[S]=1
    while (qh<qt){
        x=q[++qh]
        for (e=1;e<=edge_n;e++){
            if (fu[e]==x && fcap[e]>0 && !vis[fv[e]]){
                vis[fv[e]]=1; pe[fv[e]]=e; q[++qt]=fv[e]
            }
        }
    }
    return vis[T]
}

# ---------- residual graph of the original arcs (optimization phase) ----------
function build_residual(   i){
    E=0
    for (i=1;i<=m;i++){
        if (acap[i]-aflow[i] > 0){
            E++; eu[E]=au[i]; ev[E]=av[i]; ec[E]=acost[i]
            ecap[E]=acap[i]-aflow[i]; earc[E]=i; esgn[E]=1
        }
        if (aflow[i] > 0){
            E++; eu[E]=av[i]; ev[E]=au[i]; ec[E]=-acost[i]
            ecap[E]=aflow[i]; earc[E]=i; esgn[E]=-1
        }
    }
}

# Bellman-Ford with a virtual source (dist=0 for all).  Returns 1 and fills
# cyc_edge[1..cyc_len] with a negative residual cycle if one exists.
function find_neg_cycle(   v,it,e,changed,start,x,k){
    build_residual()
    for (v=1;v<=n;v++){ dist[v]=0; preedge[v]=0 }
    changed=0
    for (it=1;it<=n;it++){
        changed=0
        for (e=1;e<=E;e++){
            if (dist[eu[e]] + ec[e] < dist[ev[e]]){
                dist[ev[e]] = dist[eu[e]] + ec[e]
                preedge[ev[e]] = e
                changed=1
                lastv = ev[e]
            }
        }
        if (!changed) break
    }
    if (!changed) return 0
    x = lastv
    for (k=1;k<=n;k++){
        if (preedge[x] == 0) return 0
        x = eu[preedge[x]]
    }
    cyc_len=0
    start=x
    do {
        e = preedge[x]
        cyc_len++
        cyc_edge[cyc_len]=e
        x = eu[e]
    } while (x != start)
    return 1
}

# Shortest distances in residual graph (no negative cycle assumed).
function compute_potentials(   v,it,e,changed){
    build_residual()
    for (v=1;v<=n;v++) dist[v]=0
    for (it=1;it<n;it++){
        changed=0
        for (e=1;e<=E;e++){
            if (dist[eu[e]] + ec[e] < dist[ev[e]]){
                dist[ev[e]] = dist[eu[e]] + ec[e]
                changed=1
            }
        }
        if (!changed) break
    }
}

BEGIN { n=0; m=0; na=0 }

/^[ \t]*#/ { next }
/^[ \t]*c[ \t]/ { next }
/^[ \t]*$/ { next }
$1=="p" { n=$2; m=$3; next }
$1=="n" { b[$2]=$3+0; if ($2>n) n=$2; next }
$1=="a" {
    na++
    au[na]=$2+0; av[na]=$3+0; acap[na]=$4+0; acost[na]=$5+0
    aflow[na]=0
    if ($2>n) n=$2
    if ($3>n) n=$3
    next
}
END {
    m = na
    S = n+1
    T = n+2

    # ---- basic sanity ----
    tot_supply=0; tot_demand=0
    for (v=1;v<=n;v++){
        if (b[v]>0) tot_supply += b[v]
        if (b[v]<0) tot_demand += -b[v]
    }
    if (tot_supply != tot_demand){
        print "STATUS INFEASIBLE"
        print "REASON UNBALANCED"
        print "SUPPLY " tot_supply " DEMAND " tot_demand
        exit 0
    }
    total = tot_supply

    # ---- build max-flow residual ----
    edge_n=0
    for (i=1;i<=m;i++) add_pair(au[i],av[i],acap[i],i)
    for (v=1;v<=n;v++){
        if (b[v]>0) add_pair(S,v,b[v],0)
        if (b[v]<0) add_pair(v,T,-b[v],0)
    }

    # ---- Edmonds-Karp max flow ----
    flow_value=0
    while (bfs_s()){
        delta=-1
        x=T
        while (x!=S){
            e=pe[x]
            if (delta<0 || fcap[e]<delta) delta=fcap[e]
            x=fu[e]
        }
        x=T
        while (x!=S){
            e=pe[x]
            fcap[e]      -= delta
            fcap[frev[e]]+= delta
            if (farc[e]>0) aflow[farc[e]] += fsgn[e]*delta
            x=fu[e]
        }
        flow_value += delta
    }

    if (flow_value < total){
        # min cut: nodes reachable from S in the final residual graph
        bfs_s() > 0   # recomputes vis[]/pe[] (path may or may not exist)
        printf "STATUS INFEASIBLE\nREASON CUT\nWITNESS"
        lhs=0; rhs=0
        for (v=1;v<=n;v++) if (vis[v]){ printf " %d", v; lhs += b[v] }
        printf "\n"
        for (i=1;i<=m;i++){
            if (vis[au[i]] && !vis[av[i]]) rhs += acap[i]
        }
        printf "LHS %d RHS %d\n", lhs, rhs
        exit 0
    }

    # ---- cycle cancelling to optimality ----
    guard=0
    while (find_neg_cycle()){
        delta=-1
        for (k=1;k<=cyc_len;k++){
            e=cyc_edge[k]
            if (delta<0 || ecap[e]<delta) delta=ecap[e]
        }
        for (k=1;k<=cyc_len;k++){
            e=cyc_edge[k]
            aflow[earc[e]] += esgn[e]*delta
        }
        guard++
        if (guard > 1000000){ print "STATUS ERROR CYCLE_CANCEL_DIVERGED" > "/dev/stderr"; exit 2 }
    }

    # ---- dual potentials ----
    compute_potentials()

    # ---- emit ----
    cost=0
    for (i=1;i<=m;i++) cost += aflow[i]*acost[i]
    print "STATUS OPTIMAL"
    print "TOTAL_COST " cost
    for (i=1;i<=m;i++)
        printf "f %d %d %d %d %d\n", au[i], av[i], aflow[i], acap[i], acost[i]
    for (v=1;v<=n;v++)
        printf "pi %d %d\n", v, dist[v]
}

`check.awk` — independent verifier (no re-solving)

# check.awk -- independent certificate checker (no re-solving)
# Reads a merged stream: the network description followed by the solver output.
# Prints "CERT OK" or "CERT FAIL: <reason>".

/^[ \t]*#/ { next }
/^[ \t]*c[ \t]/ { next }
/^[ \t]*$/ { next }

$1=="p"  { n=$2; nm=$3; next }
$1=="n"  { b[$2]=$3+0; next }
$1=="a"  { na++; au[na]=$2+0; av[na]=$3+0; acap[na]=$4+0; acost[na]=$5+0; next }

$1=="STATUS"     { status=$2; next }
$1=="REASON"     { reason=$2; next }
$1=="SUPPLY"     { osup=$2; odem=$4; next }
$1=="DEMAND"     { odem=$3; next }
$1=="WITNESS"    { nw=0; for (i=2;i<=NF;i++){ nw++; inw[$i]=1 } next }
$1=="LHS"        { lhs=$2; rhs=$4; next }
$1=="TOTAL_COST" { total_cost=$2; next }
$1=="f" {
    fi++
    fu[fi]=$2+0; fv[fi]=$3+0; ff[fi]=$4+0; fcap[fi]=$5+0; fcost[fi]=$6+0
    next
}
$1=="pi" { pi[$2]=$3+0; next }

function fail(msg){ print "CERT FAIL: " msg; failed=1; exit 1 }

END {
    if (failed) exit 1
    if (status == "OPTIMAL") {
        if (fi != na) fail("arc count mismatch: network " na ", certificate " fi)
        # bounds, arc identity, complementary slackness, dual feasibility
        for (i=1;i<=na;i++){
            if (fu[i]!=au[i] || fv[i]!=av[i]) fail("arc " i " endpoints differ")
            if (fcap[i]!=acap[i] || fcost[i]!=acost[i]) fail("arc " i " cap/cost differ")
            if (ff[i] < 0 || ff[i] > acap[i]) fail("arc " i " flow " ff[i] " outside [0," acap[i] "]")
            rc = acost[i] + pi[au[i]] - pi[av[i]]
            if (ff[i] < acap[i] && rc < 0) fail("arc " i " forward reduced cost " rc " < 0")
            if (ff[i] > 0 && -rc < 0) fail("arc " i " backward reduced cost " (-rc) " < 0")
            if (ff[i] > 0 && ff[i] < acap[i] && rc != 0) fail("arc " i " complementary slackness rc=" rc)
        }
        # conservation
        cost=0
        for (i=1;i<=na;i++){
            charge[au[i]] += ff[i]
            charge[av[i]] -= ff[i]
            cost += ff[i]*acost[i]
        }
        for (v=1;v<=n;v++){
            if (charge[v] != b[v])
                fail("node " v " conservation " charge[v] " != supply " b[v])
        }
        if (cost != total_cost) fail("cost " cost " != declared " total_cost)
        print "CERT OK OPTIMAL cost=" cost
        exit 0
    }
    if (status == "INFEASIBLE") {
        if (reason == "UNBALANCED") {
            sup=0; dem=0
            for (v=1;v<=n;v++){ if (b[v]>0) sup+=b[v]; if (b[v]<0) dem+=-b[v] }
            if (sup == dem) fail("UNBALANCED claimed but supplies balance")
            if (osup != sup || odem != dem) fail("SUPPLY/DEMAND mismatch")
            print "CERT OK INFEASIBLE (unbalanced: supply " sup " demand " dem ")"
            exit 0
        }
        if (reason == "CUT") {
            if (nw < 1) fail("empty witness set")
            ls=0
            for (v=1;v<=n;v++) if (inw[v]) ls += b[v]
            rs=0
            for (i=1;i<=na;i++) if (inw[au[i]] && !inw[av[i]]) rs += acap[i]
            if (ls != lhs) fail("declared LHS " lhs " but computed " ls)
            if (rs != rhs) fail("declared RHS " rhs " but computed " rs)
            if (!(ls > rs)) fail("witness does not violate: " ls " <= " rs)
            print "CERT OK INFEASIBLE (cut " ls " > " rs ")"
            exit 0
        }
        fail("unknown infeasibility reason '" reason "'")
    }
    fail("unknown/absent STATUS '" status "'")
}

`mcf.sh` — run the solver

#!/bin/sh
# mcf.sh -- run the exact integer min-cost flow solver.
# Usage: mcf.sh NETWORK
set -eu
here=$(CDPATH= cd -- "$(dirname -- "$0")" && pwd)
exec awk -f "$here/mcf.awk" "$@"

`verify.sh` — solve and check in one shot

#!/bin/sh
# verify.sh -- solve and independently check the certificate in one shot.
# Usage: verify.sh NETWORK
set -eu
here=$(CDPATH= cd -- "$(dirname -- "$0")" && pwd)
net=$1
{ cat "$net"; awk -f "$here/mcf.awk" "$net"; } | awk -f "$here/check.awk"

Make them executable and run:

chmod +x mcf.sh verify.sh
./mcf.sh  network.txt          # solver output only
./verify.sh network.txt        # solver output + CERT OK / CERT FAIL verdict

Verification

1. Worked example — negative cost and partial load

tests/reroute.net:

Solver output and independent check:

$ ./verify.sh tests/reroute.net
STATUS OPTIMAL
TOTAL_COST 10
f 1 2 5 10 1
f 1 3 5 10 2
f 2 3 5 5 -3
f 3 4 10 20 1
f 2 4 0 10 5
pi 1 -3
pi 2 -2
pi 3 -1
pi 4 0
CERT OK OPTIMAL cost=10

Hand check of the certificate:

Conservation at node 1: outflow 5+5=10 = supply. Node 4: inflow 10 = demand.
Arc 2→3 is saturated (f=5=cap), rc = -3 + (-2) - (-1) = -4 ≤ 0 — backward residual reduced cost 4 ≥ 0; forward residual does not exist, so no constraint.
Arc 1→2 is unsaturated (f=5<10), rc = 1 + (-3) - (-2) = 0 (complementary slackness holds). Arc 1→3: rc = 2 + (-3) - (-1) = 0. Arc 3→4: rc = 1 + (-1) - 0 = 0.
Arc 2→4 is empty (f=0), forward only; rc = 5 + (-2) - 0 = 3 ≥ 0.

All residual reduced costs are non-negative and complementary slackness holds.

2. Infeasibility with a Farkas witness

$ ./verify.sh tests/infeas.net
STATUS INFEASIBLE
REASON CUT
WITNESS 1 2
LHS 5 RHS 0
CERT OK INFEASIBLE (cut 5 > 0)

U = {1,2}: sum b = 5 while no capacity leaves U (cap_out = 0), so no flow can satisfy supply 1. The checker recomputes both sides from U and confirms 5 > 0.

3. Regression suite (all statuses)

Running ./verify.sh on every network in tests/:

big.net              CERT OK OPTIMAL cost=-13013
disconnected.net     CERT OK OPTIMAL cost=3
infeas.net           CERT OK INFEASIBLE (cut 5 > 0)
negcost.net          CERT OK OPTIMAL cost=-20
negcycle.net         CERT OK OPTIMAL cost=-15
parallel.net         CERT OK OPTIMAL cost=13
reroute.net          CERT OK OPTIMAL cost=10
selfloop.net         CERT OK OPTIMAL cost=-6
simple.net           CERT OK OPTIMAL cost=15
unbalanced.net       CERT OK INFEASIBLE (unbalanced: supply 5 demand 3)
zerocycle.net        CERT OK OPTIMAL cost=-12

These cover: negative arcs, pure negative cycles (including a 1-cycle self-loop), parallel arcs, disconnected supply/demand components, unbalanced totals, and a 40-node/160-arc instance (solved and certified in ~0.18 s).

4. Exhaustive cross-check on tiny networks

stress.py generates random tiny networks (n ≤ 5, m ≤ 6, caps 0..3, costs -3..3, random balanced supplies) and compares against brute-force enumeration of every integer flow:

$ python3 stress.py 4000
ran 4000 cases, failures=0

Every feasible case matched the brute-force minimum cost exactly, every infeasible case was confirmed infeasible by enumeration, and every emitted certificate passed check.awk. (A later run of 2000 cases also passed after a defensive guard was added.)

5. Independent feasibility cross-check

stress_feas.py implements Dinic max flow from scratch and compares the feasible/infeasible verdict on random medium networks:

$ python3 stress_feas.py
ran 2000 feas=861 inf=1139 bad=0

6. One-line reproduction

From the directory containing the four files:

printf 'p 2 1\nn 1 5\nn 2 -5\na 1 2 10 3\n' > /tmp/t.net
./verify.sh /tmp/t.net
# STATUS OPTIMAL
# TOTAL_COST 15
# f 1 2 5 10 3
# pi 1 -3
# pi 2 0
# CERT OK OPTIMAL cost=15

Notes and trade-offs

Exactness. All quantities are integers. delta on every cycle is an integer ≥ 1 (min of integer residual capacities), so flows stay integral and the optimum is exact.
Complexity. Feasibility is Edmonds–Karp O(V·E²); optimization is cycle canceling with a Bellman–Ford search per cycle (pseudopolynomial, but fast for the instance sizes here). The guard counter turns any pathological blow-up into an explicit STATUS ERROR rather than a silent hang.
No lower bounds. Arcs are 0 ≤ f ≤ cap. Lower bounds can be supported by the standard substitution f' = f - l, adjusting node supplies by Σl.
Potential overflow. mawk uses doubles; all test values are far inside exact-integer range (|x| < 2^53).
Independence. check.awk never runs the flow algorithm; it only re-evaluates the certificate, so it can be used to audit output from any solver implementing this format.

Summary

Root causes fixed: negative costs (cycle canceling), infeasibility without witness (Farkas min-cut), missing optimality proof (dual potentials + complementary slackness), unbalanced/disconnected networks, and floating-point/rounding.
Exact fix: four runnable files (mcf.awk, check.awk, mcf.sh, verify.sh) in ~/solution/.
Verification: 11-case regression suite, 4000 + 2000 exhaustive brute-force comparisons with zero failures, 2000-case independent Dinic feasibility cross-check, and a worked hand-checked certificate.

Evidence & signatures

# Evidence
- Problem class: bash-exact-min-cost-flow-dual-optimality-certificate
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-20T23:05:56.419Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement an exact integer min-cost flow solver in POSIX shell with coreutils/awk that reads a capacitated network and emits the optimal flow together with a dual potential certificate, verifying complementary slackness on every arc. The solver must handle negative arc costs, disconnected supply components, and infeasibility detection with a Farkas-style witness instead of a generic error. Terminate with a machine-checkable proof that no negative-cost residual cycle exists under the final potentials, so an independent checker can confirm optimality without re-solving.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "bash-exact-min-cost-flow-dual-optimality-certificate", "provider": "openrouter", "solved_at": "2026-09-20T23:05:56.432Z", "version": "5.2"}

Answer 2

The solution has been implemented and verified. The complete deliverable is saved at ~/solution/SOLUTION.md (with runnable artifacts alongside it). Here is the solution:

Exact Integer Min-Cost Flow in POSIX Shell/awk with a Machine-Checkable Dual Certificate

TL;DR

A min-cost flow solver written in POSIX awk (runs under mawk, which ships on this box) that

reads a capacitated network with negative arc costs,
detects infeasibility with a Farkas cut witness instead of a generic error,
emits an optimal integral flow and dual node potentials, and
ships an independent checker that proves optimality by verifying flow conservation, bounds, non-negative reduced costs, and complementary slackness — without re-solving.

The complete, tested implementation is in ~/solution/: mcf.awk (solver), check.awk (checker), mcf.sh / verify.sh (wrappers). No GNU-only awk features are used.

Root-cause analysis

The "problem" here is a specification, not a pre-existing broken script. What makes a naive shell implementation fail is a specific set of traps, each addressed explicitly:

#	Failure mode of naive approach	Why it breaks	Fix used here
1	Greedy/Dijkstra augmentation	Negative costs make Dijkstra invalid; greedy first paths are not the cheapest	Feasibility first (cost-blind max flow), then cycle canceling on the residual graph
2	Cycle canceling from zero flow	A feasible flow must exist first	Add super-source/sink and run Edmonds–Karp max flow to obtain a feasible flow
3	Reporting "infeasible" as a string	No witness → cannot be independently checked	Emit the min-cut set `U` with `sum(b over U) > cap_out(U)` (Farkas certificate)
4	Ignoring unbalanced supplies	Conservation forces `sum(b) == 0`; otherwise there is no solution regardless of arcs	Detect `total_supply != total_demand` and emit an `UNBALANCED` proof
5	Just printing a flow	A flow alone does not prove optimality	Emit dual potentials `pi` so an external checker can verify reduced costs
6	Floating point / rounding	"Exact" requires integers	All arithmetic is integer; every augmentation uses an integer `delta >= 1`
7	Disconnected components	A single-source pass may miss one component	Super-source connects every supply, covering all components
8	Negative residual cycles	If they remain, the flow is not optimal	Bellman–Ford (virtual source) finds and cancels them until none remain

Why the certificate is a real proof

rc(u,v) ≥ 0  whenever f(u,v) < u(u,v)     (forward residual arc exists)
rc(u,v) ≤ 0  whenever f(u,v) > 0          (backward residual arc exists)

Input / output contract

Input (stdin / file), whitespace separated, #/c comments and blank lines ignored:

c comment
p N M                 N nodes numbered 1..N, M arcs
n v b                 node v supply b  (b > 0 supply, b < 0 demand)
a u v cap cost        directed arc u->v, 0 <= flow <= cap, integer cost

Output — optimal:

STATUS OPTIMAL
TOTAL_COST <int>
f <u> <v> <flow> <cap> <cost>     one line per input arc, same order
pi <v> <potential>

Output — infeasible:

STATUS INFEASIBLE
REASON UNBALANCED                  (supply != demand)
SUPPLY <total> DEMAND <total>

   - or -

STATUS INFEASIBLE
REASON CUT
WITNESS <v1> <v2> ...
LHS <sum b over witness> RHS <capacity leaving witness>

The exact fix (code)

`mcf.awk` — solver

# mcf.awk -- exact integer min-cost flow solver with dual certificate
# Input (stdin):
#   c <comment>                 ignored
#   p <N> <M>                   N nodes (1..N), M arcs (optional; M is read)
#   n <v> <b>                   node supply (b>0 supply, b<0 demand)
#   a <u> <v> <cap> <cost>      directed arc u->v, 0<=flow<=cap, integer cost
#
# Output:
#   If unbalanced/infeasible:
#     STATUS INFEASIBLE
#     REASON UNBALANCED | CUT
#     SUPPLY <total> DEMAND <total>            (UNBALANCED only)
#     WITNESS <v1> <v2> ...                     (CUT only)
#     LHS <sum b over witness> RHS <cap leaving witness>
#   If feasible:
#     STATUS OPTIMAL
#     TOTAL_COST <integer>
#     f <u> <v> <flow> <cap> <cost>
#     pi <v> <potential>

function min(a,b){ return a<b ? a : b }

# ---------- max-flow residual edge storage (feasibility phase) ----------
function add_pair(u,v,cap,arc,   k){
    k = edge_n + 1
    edge_n++
    fu[k]=u; fv[k]=v; fcap[k]=cap; farc[k]=arc; fsgn[k]=1
    edge_n++
    fu[edge_n]=v; fv[edge_n]=u; fcap[edge_n]=0; farc[edge_n]=arc; fsgn[edge_n]=-1
    frev[k]=edge_n; frev[edge_n]=k
    return k
}

function bfs_s(   qh,qt,x,e){
    for (i=1;i<=n+2;i++){ vis[i]=0; pe[i]=0 }
    qh=0; qt=0; q[++qt]=S; vis[S]=1
    while (qh<qt){
        x=q[++qh]
        for (e=1;e<=edge_n;e++){
            if (fu[e]==x && fcap[e]>0 && !vis[fv[e]]){
                vis[fv[e]]=1; pe[fv[e]]=e; q[++qt]=fv[e]
            }
        }
    }
    return vis[T]
}

# ---------- residual graph of the original arcs (optimization phase) ----------
function build_residual(   i){
    E=0
    for (i=1;i<=m;i++){
        if (acap[i]-aflow[i] > 0){
            E++; eu[E]=au[i]; ev[E]=av[i]; ec[E]=acost[i]
            ecap[E]=acap[i]-aflow[i]; earc[E]=i; esgn[E]=1
        }
        if (aflow[i] > 0){
            E++; eu[E]=av[i]; ev[E]=au[i]; ec[E]=-acost[i]
            ecap[E]=aflow[i]; earc[E]=i; esgn[E]=-1
        }
    }
}

# Bellman-Ford with a virtual source (dist=0 for all).  Returns 1 and fills
# cyc_edge[1..cyc_len] with a negative residual cycle if one exists.
function find_neg_cycle(   v,it,e,changed,start,x,k){
    build_residual()
    for (v=1;v<=n;v++){ dist[v]=0; preedge[v]=0 }
    changed=0
    for (it=1;it<=n;it++){
        changed=0
        for (e=1;e<=E;e++){
            if (dist[eu[e]] + ec[e] < dist[ev[e]]){
                dist[ev[e]] = dist[eu[e]] + ec[e]
                preedge[ev[e]] = e
                changed=1
                lastv = ev[e]
            }
        }
        if (!changed) break
    }
    if (!changed) return 0
    x = lastv
    for (k=1;k<=n;k++){
        if (preedge[x] == 0) return 0
        x = eu[preedge[x]]
    }
    cyc_len=0
    start=x
    do {
        e = preedge[x]
        cyc_len++
        cyc_edge[cyc_len]=e
        x = eu[e]
    } while (x != start)
    return 1
}

# Shortest distances in residual graph (no negative cycle assumed).
function compute_potentials(   v,it,e,changed){
    build_residual()
    for (v=1;v<=n;v++) dist[v]=0
    for (it=1;it<n;it++){
        changed=0
        for (e=1;e<=E;e++){
            if (dist[eu[e]] + ec[e] < dist[ev[e]]){
                dist[ev[e]] = dist[eu[e]] + ec[e]
                changed=1
            }
        }
        if (!changed) break
    }
}

BEGIN { n=0; m=0; na=0 }

/^[ \t]*#/ { next }
/^[ \t]*c[ \t]/ { next }
/^[ \t]*$/ { next }
$1=="p" { n=$2; m=$3; next }
$1=="n" { b[$2]=$3+0; if ($2>n) n=$2; next }
$1=="a" {
    na++
    au[na]=$2+0; av[na]=$3+0; acap[na]=$4+0; acost[na]=$5+0
    aflow[na]=0
    if ($2>n) n=$2
    if ($3>n) n=$3
    next
}
END {
    m = na
    S = n+1
    T = n+2

    # ---- basic sanity ----
    tot_supply=0; tot_demand=0
    for (v=1;v<=n;v++){
        if (b[v]>0) tot_supply += b[v]
        if (b[v]<0) tot_demand += -b[v]
    }
    if (tot_supply != tot_demand){
        print "STATUS INFEASIBLE"
        print "REASON UNBALANCED"
        print "SUPPLY " tot_supply " DEMAND " tot_demand
        exit 0
    }
    total = tot_supply

    # ---- build max-flow residual ----
    edge_n=0
    for (i=1;i<=m;i++) add_pair(au[i],av[i],acap[i],i)
    for (v=1;v<=n;v++){
        if (b[v]>0) add_pair(S,v,b[v],0)
        if (b[v]<0) add_pair(v,T,-b[v],0)
    }

    # ---- Edmonds-Karp max flow ----
    flow_value=0
    while (bfs_s()){
        delta=-1
        x=T
        while (x!=S){
            e=pe[x]
            if (delta<0 || fcap[e]<delta) delta=fcap[e]
            x=fu[e]
        }
        x=T
        while (x!=S){
            e=pe[x]
            fcap[e]      -= delta
            fcap[frev[e]]+= delta
            if (farc[e]>0) aflow[farc[e]] += fsgn[e]*delta
            x=fu[e]
        }
        flow_value += delta
    }

    if (flow_value < total){
        # min cut: nodes reachable from S in the final residual graph
        bfs_s() > 0   # recomputes vis[]/pe[] (path may or may not exist)
        printf "STATUS INFEASIBLE\nREASON CUT\nWITNESS"
        lhs=0; rhs=0
        for (v=1;v<=n;v++) if (vis[v]){ printf " %d", v; lhs += b[v] }
        printf "\n"
        for (i=1;i<=m;i++){
            if (vis[au[i]] && !vis[av[i]]) rhs += acap[i]
        }
        printf "LHS %d RHS %d\n", lhs, rhs
        exit 0
    }

    # ---- cycle cancelling to optimality ----
    guard=0
    while (find_neg_cycle()){
        delta=-1
        for (k=1;k<=cyc_len;k++){
            e=cyc_edge[k]
            if (delta<0 || ecap[e]<delta) delta=ecap[e]
        }
        for (k=1;k<=cyc_len;k++){
            e=cyc_edge[k]
            aflow[earc[e]] += esgn[e]*delta
        }
        guard++
        if (guard > 1000000){ print "STATUS ERROR CYCLE_CANCEL_DIVERGED" > "/dev/stderr"; exit 2 }
    }

    # ---- dual potentials ----
    compute_potentials()

    # ---- emit ----
    cost=0
    for (i=1;i<=m;i++) cost += aflow[i]*acost[i]
    print "STATUS OPTIMAL"
    print "TOTAL_COST " cost
    for (i=1;i<=m;i++)
        printf "f %d %d %d %d %d\n", au[i], av[i], aflow[i], acap[i], acost[i]
    for (v=1;v<=n;v++)
        printf "pi %d %d\n", v, dist[v]
}

`check.awk` — independent verifier (no re-solving)

# check.awk -- independent certificate checker (no re-solving)
# Reads a merged stream: the network description followed by the solver output.
# Prints "CERT OK" or "CERT FAIL: <reason>".

/^[ \t]*#/ { next }
/^[ \t]*c[ \t]/ { next }
/^[ \t]*$/ { next }

$1=="p"  { n=$2; nm=$3; next }
$1=="n"  { b[$2]=$3+0; next }
$1=="a"  { na++; au[na]=$2+0; av[na]=$3+0; acap[na]=$4+0; acost[na]=$5+0; next }

$1=="STATUS"     { status=$2; next }
$1=="REASON"     { reason=$2; next }
$1=="SUPPLY"     { osup=$2; odem=$4; next }
$1=="DEMAND"     { odem=$3; next }
$1=="WITNESS"    { nw=0; for (i=2;i<=NF;i++){ nw++; inw[$i]=1 } next }
$1=="LHS"        { lhs=$2; rhs=$4; next }
$1=="TOTAL_COST" { total_cost=$2; next }
$1=="f" {
    fi++
    fu[fi]=$2+0; fv[fi]=$3+0; ff[fi]=$4+0; fcap[fi]=$5+0; fcost[fi]=$6+0
    next
}
$1=="pi" { pi[$2]=$3+0; next }

function fail(msg){ print "CERT FAIL: " msg; failed=1; exit 1 }

END {
    if (failed) exit 1
    if (status == "OPTIMAL") {
        if (fi != na) fail("arc count mismatch: network " na ", certificate " fi)
        # bounds, arc identity, complementary slackness, dual feasibility
        for (i=1;i<=na;i++){
            if (fu[i]!=au[i] || fv[i]!=av[i]) fail("arc " i " endpoints differ")
            if (fcap[i]!=acap[i] || fcost[i]!=acost[i]) fail("arc " i " cap/cost differ")
            if (ff[i] < 0 || ff[i] > acap[i]) fail("arc " i " flow " ff[i] " outside [0," acap[i] "]")
            rc = acost[i] + pi[au[i]] - pi[av[i]]
            if (ff[i] < acap[i] && rc < 0) fail("arc " i " forward reduced cost " rc " < 0")
            if (ff[i] > 0 && -rc < 0) fail("arc " i " backward reduced cost " (-rc) " < 0")
            if (ff[i] > 0 && ff[i] < acap[i] && rc != 0) fail("arc " i " complementary slackness rc=" rc)
        }
        # conservation
        cost=0
        for (i=1;i<=na;i++){
            charge[au[i]] += ff[i]
            charge[av[i]] -= ff[i]
            cost += ff[i]*acost[i]
        }
        for (v=1;v<=n;v++){
            if (charge[v] != b[v])
                fail("node " v " conservation " charge[v] " != supply " b[v])
        }
        if (cost != total_cost) fail("cost " cost " != declared " total_cost)
        print "CERT OK OPTIMAL cost=" cost
        exit 0
    }
    if (status == "INFEASIBLE") {
        if (reason == "UNBALANCED") {
            sup=0; dem=0
            for (v=1;v<=n;v++){ if (b[v]>0) sup+=b[v]; if (b[v]<0) dem+=-b[v] }
            if (sup == dem) fail("UNBALANCED claimed but supplies balance")
            if (osup != sup || odem != dem) fail("SUPPLY/DEMAND mismatch")
            print "CERT OK INFEASIBLE (unbalanced: supply " sup " demand " dem ")"
            exit 0
        }
        if (reason == "CUT") {
            if (nw < 1) fail("empty witness set")
            ls=0
            for (v=1;v<=n;v++) if (inw[v]) ls += b[v]
            rs=0
            for (i=1;i<=na;i++) if (inw[au[i]] && !inw[av[i]]) rs += acap[i]
            if (ls != lhs) fail("declared LHS " lhs " but computed " ls)
            if (rs != rhs) fail("declared RHS " rhs " but computed " rs)
            if (!(ls > rs)) fail("witness does not violate: " ls " <= " rs)
            print "CERT OK INFEASIBLE (cut " ls " > " rs ")"
            exit 0
        }
        fail("unknown infeasibility reason '" reason "'")
    }
    fail("unknown/absent STATUS '" status "'")
}

`mcf.sh` — run the solver

#!/bin/sh
# mcf.sh -- run the exact integer min-cost flow solver.
# Usage: mcf.sh NETWORK
set -eu
here=$(CDPATH= cd -- "$(dirname -- "$0")" && pwd)
exec awk -f "$here/mcf.awk" "$@"

`verify.sh` — solve and check in one shot

#!/bin/sh
# verify.sh -- solve and independently check the certificate in one shot.
# Usage: verify.sh NETWORK
set -eu
here=$(CDPATH= cd -- "$(dirname -- "$0")" && pwd)
net=$1
{ cat "$net"; awk -f "$here/mcf.awk" "$net"; } | awk -f "$here/check.awk"

Make them executable and run:

chmod +x mcf.sh verify.sh
./mcf.sh  network.txt          # solver output only
./verify.sh network.txt        # solver output + CERT OK / CERT FAIL verdict

Verification

1. Worked example — negative cost and partial load

tests/reroute.net:

Solver output and independent check:

$ ./verify.sh tests/reroute.net
STATUS OPTIMAL
TOTAL_COST 10
f 1 2 5 10 1
f 1 3 5 10 2
f 2 3 5 5 -3
f 3 4 10 20 1
f 2 4 0 10 5
pi 1 -3
pi 2 -2
pi 3 -1
pi 4 0
CERT OK OPTIMAL cost=10

Hand check of the certificate:

Conservation at node 1: outflow 5+5=10 = supply. Node 4: inflow 10 = demand.
Arc 2→3 is saturated (f=5=cap), rc = -3 + (-2) - (-1) = -4 ≤ 0 — backward residual reduced cost 4 ≥ 0; forward residual does not exist, so no constraint.
Arc 1→2 is unsaturated (f=5<10), rc = 1 + (-3) - (-2) = 0 (complementary slackness holds). Arc 1→3: rc = 2 + (-3) - (-1) = 0. Arc 3→4: rc = 1 + (-1) - 0 = 0.
Arc 2→4 is empty (f=0), forward only; rc = 5 + (-2) - 0 = 3 ≥ 0.

All residual reduced costs are non-negative and complementary slackness holds.

2. Infeasibility with a Farkas witness

$ ./verify.sh tests/infeas.net
STATUS INFEASIBLE
REASON CUT
WITNESS 1 2
LHS 5 RHS 0
CERT OK INFEASIBLE (cut 5 > 0)

U = {1,2}: sum b = 5 while no capacity leaves U (cap_out = 0), so no flow can satisfy supply 1. The checker recomputes both sides from U and confirms 5 > 0.

3. Regression suite (all statuses)

Running ./verify.sh on every network in tests/:

big.net              CERT OK OPTIMAL cost=-13013
disconnected.net     CERT OK OPTIMAL cost=3
infeas.net           CERT OK INFEASIBLE (cut 5 > 0)
negcost.net          CERT OK OPTIMAL cost=-20
negcycle.net         CERT OK OPTIMAL cost=-15
parallel.net         CERT OK OPTIMAL cost=13
reroute.net          CERT OK OPTIMAL cost=10
selfloop.net         CERT OK OPTIMAL cost=-6
simple.net           CERT OK OPTIMAL cost=15
unbalanced.net       CERT OK INFEASIBLE (unbalanced: supply 5 demand 3)
zerocycle.net        CERT OK OPTIMAL cost=-12

4. Exhaustive cross-check on tiny networks

stress.py generates random tiny networks (n ≤ 5, m ≤ 6, caps 0..3, costs -3..3, random balanced supplies) and compares against brute-force enumeration of every integer flow:

$ python3 stress.py 4000
ran 4000 cases, failures=0

5. Independent feasibility cross-check

stress_feas.py implements Dinic max flow from scratch and compares the feasible/infeasible verdict on random medium networks:

$ python3 stress_feas.py
ran 2000 feas=861 inf=1139 bad=0

6. One-line reproduction

From the directory containing the four files:

printf 'p 2 1\nn 1 5\nn 2 -5\na 1 2 10 3\n' > /tmp/t.net
./verify.sh /tmp/t.net
# STATUS OPTIMAL
# TOTAL_COST 15
# f 1 2 5 10 3
# pi 1 -3
# pi 2 0
# CERT OK OPTIMAL cost=15

Notes and trade-offs

Exactness. All quantities are integers. delta on every cycle is an integer ≥ 1 (min of integer residual capacities), so flows stay integral and the optimum is exact.
Complexity. Feasibility is Edmonds–Karp O(V·E²); optimization is cycle canceling with a Bellman–Ford search per cycle (pseudopolynomial, but fast for the instance sizes here). The guard counter turns any pathological blow-up into an explicit STATUS ERROR rather than a silent hang.
No lower bounds. Arcs are 0 ≤ f ≤ cap. Lower bounds can be supported by the standard substitution f' = f - l, adjusting node supplies by Σl.
Potential overflow. mawk uses doubles; all test values are far inside exact-integer range (|x| < 2^53).
Independence. check.awk never runs the flow algorithm; it only re-evaluates the certificate, so it can be used to audit output from any solver implementing this format.

Summary

Root causes fixed: negative costs (cycle canceling), infeasibility without witness (Farkas min-cut), missing optimality proof (dual potentials + complementary slackness), unbalanced/disconnected networks, and floating-point/rounding.
Exact fix: four runnable files (mcf.awk, check.awk, mcf.sh, verify.sh) in ~/solution/.
Verification: 11-case regression suite, 4000 + 2000 exhaustive brute-force comparisons with zero failures, 2000-case independent Dinic feasibility cross-check, and a worked hand-checked certificate.

Evidence & signatures

# Evidence
- Problem class: bash-exact-min-cost-flow-dual-optimality-certificate
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-20T23:05:56.419Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement an exact integer min-cost flow solver in POSIX shell with coreutils/awk that reads a capacitated network and emits the optimal flow together with a dual potential certificate, verifying complementary slackness on every arc. The solver must handle negative arc costs, disconnected supply components, and infeasibility detection with a Farkas-style witness instead of a generic error. Terminate with a machine-checkable proof that no negative-cost residual cycle exists under the final potentials, so an independent checker can confirm optimality without re-solving.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "bash-exact-min-cost-flow-dual-optimality-certificate", "provider": "openrouter", "solved_at": "2026-09-20T23:05:56.432Z", "version": "5.2"}

Generated from the verified corpus · MIT licensedBack to the catalog

bash-exact-min-cost-flow-dual-optimality-certificate

Answer 1

Exact Integer Min-Cost Flow in POSIX Shell/awk with a Machine-Checkable Dual Certificate

TL;DR

Root-cause analysis

Why the certificate is a real proof

Input / output contract

The exact fix (code)

mcf.awk — solver

check.awk — independent verifier (no re-solving)

mcf.sh — run the solver

verify.sh — solve and check in one shot

Verification

1. Worked example — negative cost and partial load

2. Infeasibility with a Farkas witness

3. Regression suite (all statuses)

4. Exhaustive cross-check on tiny networks

5. Independent feasibility cross-check

6. One-line reproduction

Notes and trade-offs

Summary

Evidence & signatures

Answer 2

Exact Integer Min-Cost Flow in POSIX Shell/awk with a Machine-Checkable Dual Certificate

TL;DR

Root-cause analysis

Why the certificate is a real proof

Input / output contract

The exact fix (code)

mcf.awk — solver

check.awk — independent verifier (no re-solving)

mcf.sh — run the solver

verify.sh — solve and check in one shot

Verification

1. Worked example — negative cost and partial load

2. Infeasibility with a Farkas witness

3. Regression suite (all statuses)

4. Exhaustive cross-check on tiny networks

5. Independent feasibility cross-check

6. One-line reproduction

Notes and trade-offs

Summary

Evidence & signatures

`mcf.awk` — solver

`check.awk` — independent verifier (no re-solving)

`mcf.sh` — run the solver

`verify.sh` — solve and check in one shot

`mcf.awk` — solver

`check.awk` — independent verifier (no re-solving)

`mcf.sh` — run the solver

`verify.sh` — solve and check in one shot