oba — Origin-based assignment (Bar-Gera 2002) on the Braess network

What. Origin-based assignment confines each origin’s flow to an acyclic subnetwork (a ‘bush’) and equilibrates within it, so it captures the whole route set of an origin without enumerating paths. Bushes give near-Newton convergence with link-order storage, the departure that made high-accuracy equilibria routine.

Why it is in the benchmark. It opens the bush-based branch of the convergence ladder ([bargera2002origin]). See its entry in the model compendium and the certificate design in docs/ARCHITECTURE.md (P1).

Scope. This notebook runs the solver on the built-in Braess scenario (5 links, one OD pair, no download) and certifies the result; it does not benchmark solver families against each other — for that, see demos/demo_quickstart.py.

Primary reference: [bargera2002origin] (docs/REFERENCES.md).

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. `oba` 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 (
    Budget,
    Evaluator,
    OriginBasedModel,
    RngBundle,
    Trace,
    braess_scenario,
    viz,
)

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 = OriginBasedModel()
bundle = model.solve(scenario, Budget(iterations=50), 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)}")
print(f"self-reported gap: {final.self_report['relative_gap']:.3e}  (provenance only)")

model            : oba
budget spent     : 50 iterations, 286 shortest-path calls
checkpoints      : 50
emitted flows    : [4. 2. 2. 2. 4.]
self-reported gap: 0.000e+00  (provenance only)

Certify (P1)

The harness, never the model, computes every scored metric: the relative gap is a property of (link_flows, scenario), recomputed here by the same Evaluator that scores every model in the benchmark. We also recompute the analytic Braess anchor in-cell rather than quoting it: at UE the flows are (4, 2, 2, 2, 4) and every used route costs 92 (pinned in tests/test_braess.py).

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}")
print(f"Beckmann objective     : {metrics['beckmann_objective']:.6f}")

# The origin bush equilibrates to machine precision on Braess — bush storage without
# path enumeration, the origin-based advance.
assert metrics["feasible"] == 1.0
assert abs(certified_gap) < 1e-10

# Honesty diff (P1): this white box's self-report must match the certificate.
assert np.isclose(final.self_report["relative_gap"], certified_gap, rtol=1e-9, atol=1e-12)

# Analytic anchor, recomputed in-cell.
ref_flows = np.array([4.0, 2.0, 2.0, 2.0, 4.0])
assert evaluator.evaluate(ref_flows)["relative_gap"] < 1e-6
assert np.allclose(final.link_flows, ref_flows, atol=1e-4)
route_time = metrics["tstt"] / scenario.demand.total
print(f"route time (TSTT/D)    : {route_time:.6f}  (analytic UE: 92)")
assert abs(route_time - 92.0) < 1e-3

# Certify EVERY checkpoint the same way — the trace feeds the visual below.
trace_gaps = [
    evaluator.evaluate(c.link_flows)["relative_gap"] for c in bundle.trace.checkpoints
]
print(f"checkpoints certified  : {len(trace_gaps)} "
      f"(first gap {trace_gaps[0]:.3e}, last {trace_gaps[-1]:.3e})")

certified relative gap : 0.000e+00
feasible               : 1
Beckmann objective     : 386.000008
route time (TSTT/D)    : 92.000000  (analytic UE: 92)
checkpoints certified  : 50 (first gap 2.767e-02, last 0.000e+00)

Visualize

Both figures come from tabench.viz, the house visualizer — one visual style across every tutorial, every plotted number certified above. Left/top: the certified equilibrium link flows on the Braess diamond. Right/bottom: the emitted flows against the analytic UE recomputed in the previous cell — points on the y = x guide mean the solver reproduced the certified equilibrium link-for-link.

# 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), {"oba": final.link_flows}))

Takeaways & pointers

• Certified, not self-reported. The gap above came from Evaluator, recomputed from the emitted flows here; the self-report was only diffed against it.

• Bushes, not paths. Confining each origin’s flow to an acyclic subnetwork gives near-Newton convergence with link-order storage.

• Where next. the bush-based siblings: algb · tapas; the path-based precursor: gp; link-based: bfw; the lineage in the model compendium; the full matrix via run_experiment(...) as in demos/demo_quickstart.py.