aon — All-or-nothing assignment on the Braess network

What. All-or-nothing (AON) loads every OD pair entirely onto its free-flow shortest path, ignoring how that flow raises congestion. It has no single originating paper — it is the capacity-blind pre-equilibrium practice that Beckmann’s convex equilibrium program ([beckmann1956studies]) and its Frank–Wolfe solution ([leblanc1975efficient], docs/REFERENCES.md) were created to replace. In this benchmark it is the deliberate weak baseline, and — as the linearized subproblem of Frank–Wolfe — the atom every equilibrium solver here is built from.

Why it is in the benchmark. It anchors the low end of the convergence ladder and makes P5 concrete: a baseline is scored honestly by the same certificate, never excluded. See the model compendium and docs/ARCHITECTURE.md (P1).

Scope. One AON pass on the built-in Braess scenario (5 links, one OD pair, no download). It does not converge to equilibrium — that is the point. For the solvers that do, see the fw / cfw / bfw tutorials.

How this notebook is graded

A notebook never claims a number it does not compute in that cell. Every scored quantity below is recomputed live by the P1 Evaluator from the flows the model emitted, in the cell where it is claimed. Model self-reports are shown only as provenance and diffed against the certificate as an honesty check, exactly as the harness treats them (README, Certified, not self-reported).

# Setup. `aon` is a core model: a plain `pip install -e .` suffices — no
# optional extra, so no guard cell. The inline backend is Agg-based (headless CI
# renders into the notebook); NEVER matplotlib.use("Agg") in-kernel — it silently
# suppresses inline figure capture.
%matplotlib inline
import numpy as np

from tabench import (
    AllOrNothingModel,
    Budget,
    Evaluator,
    RngBundle,
    Trace,
    braess_scenario,
    viz,
)

Matplotlib is building the font cache; this may take a moment.

The scenario

The built-in Braess network: 4 nodes, 5 links, a single OD pair (1 → 2) with demand 6. Scenarios are frozen and content-hashed (P2) — the hash printed below is the identity of the benchmark instance, so a silently edited network cannot masquerade as it.

scenario = braess_scenario()
net = scenario.network

print(f"scenario      : {scenario.name}")
print(f"content hash  : {scenario.content_hash()[:16]}…")
print(f"links         : {net.n_links}  (tail→head: "
      + ", ".join(f"{i}->{j}" for i, j in zip(net.init_node, net.term_node)) + ")")
print(f"total demand  : {scenario.demand.total}")

scenario      : braess
content hash  : cf00f411cdccec88…
links         : 5  (tail→head: 1->3, 1->4, 3->4, 3->2, 4->2)
total demand  : 6.0

Solve

The model contract (CONTRIBUTING.md): a model receives (scenario, budget, rng, trace), records checkpoints, and respects the budget. Budgets are hardware-free (iterations / shortest-path calls; wall-clock is recorded but never the ranking axis, P7). Whatever the model writes into self_report is provenance, not a score.

model = AllOrNothingModel()
bundle = model.solve(scenario, Budget(iterations=1), RngBundle(0), Trace())

final = bundle.final
print(f"model            : {model.name}")
print(f"budget spent     : {final.coords.iterations} iterations, "
      f"{final.coords.sp_calls} shortest-path calls")
print(f"checkpoints      : {len(bundle.trace.checkpoints)}")
print(f"emitted flows    : {np.round(final.link_flows, 6)}")

model            : aon
budget spent     : 1 iterations, 1 shortest-path calls
checkpoints      : 1
emitted flows    : [6. 0. 6. 0. 6.]

Certify (P1)

The harness scores AON with the identical certificate it applies to Frank–Wolfe: the relative gap is a property of (link_flows, scenario). AON is a heuristic — provides_gap=False, so it self-reports no gap; the certificate is the only number, and it is honestly large. We recompute the analytic UE anchor in-cell to show that AON’s loading is not the equilibrium (flows (4, 2, 2, 2, 4), route time 92).

evaluator = Evaluator(scenario)
metrics = evaluator.evaluate(final.link_flows)

certified_gap = metrics["relative_gap"]
print(f"certified relative gap : {certified_gap:.3e}")
print(f"feasible               : {metrics['feasible']:.0f}")

# AON loads all demand on the free-flow shortest path: demand-feasible (audit
# passes) but far from equilibrium, so the certified gap is large — and honest.
assert metrics["feasible"] == 1.0
assert certified_gap > 0.1

# `aon` self-reports no gap (provides_gap=False), so there is nothing to diff —
# the certificate stands alone.
assert "relative_gap" not in final.self_report

# Analytic anchor, recomputed in-cell: the TRUE UE flows (4,2,2,2,4) carry a
# ~machine-zero gap, and AON's loading differs from them — the gap is real.
ref_flows = np.array([4.0, 2.0, 2.0, 2.0, 4.0])
assert evaluator.evaluate(ref_flows)["relative_gap"] < 1e-6
assert not np.allclose(final.link_flows, ref_flows, atol=1e-1)
loaded = [f"{i}->{j}" for i, j, v in zip(net.init_node, net.term_node, final.link_flows) if v > 0]
print(f"AON loaded route links : {loaded}")
print(f"analytic UE flows       : {ref_flows}  (gap {evaluator.evaluate(ref_flows)['relative_gap']:.1e})")

# The UE route time quoted above (92), recomputed from ref_flows -- NOT final.link_flows,
# since AON is off-equilibrium and its own TSTT/D is not the analytic anchor.
route_time = evaluator.evaluate(ref_flows)["tstt"] / scenario.demand.total
print(f"analytic UE route time  : {route_time:.6f}  (TSTT/D at ref_flows)")
assert abs(route_time - 92.0) < 1e-3

certified relative gap : 1.912e-01
feasible               : 1
AON loaded route links : ['1->3', '3->4', '4->2']
analytic UE flows       : [4. 2. 2. 2. 4.]  (gap 3.6e-09)
analytic UE route time  : 92.000001  (TSTT/D at ref_flows)

Visualize

Both figures come from tabench.viz. Left/top: AON’s link loading on the Braess diamond — all six units pile onto one path. Right/bottom: AON’s flows against the analytic UE recomputed above; the points sit off the y = x guide, which is the certified gap made visual — a baseline scored honestly, not hidden.

# Certified equilibrium flows on the network (house style via tabench.viz).
display(viz.plot_network_flows(net, final.link_flows))

# Emitted flows vs the analytic UE recomputed above (off-diagonal == disagreement).
display(viz.plot_flow_scatter(("analytic UE", ref_flows), {"aon": final.link_flows}))

Takeaways & pointers

• Scored, not excluded (P5). AON’s gap above came from the same Evaluator that scores every model here; it is large because AON ignores congestion, and that is reported honestly rather than hidden.

• The atom of the solvers. One AON pass is exactly Frank–Wolfe’s linearized subproblem — iterate it with a line search and you get fw.

• Where next. The solvers that converge: msa · fw · cfw · bfw; the lineage in the model compendium; the full matrix via run_experiment(...) as in demos/demo_quickstart.py.