algb — Algorithm B (Dial 2006) on the Braess network

What. Algorithm B is the bush-based method that shifts flow between the longest and shortest used segments of each origin bush, restructuring the bush as costs change. It refined origin-based assignment into the reliably machine-precision UE solver, still link-order storage per origin.

Why it is in the benchmark. It is the bush-based workhorse of the convergence race ([dial2006path]). 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: [dial2006path] (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. `algb` 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 (
    AlgorithmBModel,
    Budget,
    Evaluator,
    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 = AlgorithmBModel()
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            : algb
budget spent     : 50 iterations, 173 shortest-path calls
checkpoints      : 50
emitted flows    : [4. 2. 2. 2. 4.]
self-reported gap: -2.060e-16  (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}")

# Algorithm B's max/min-segment bush shifts reach machine precision on Braess — the
# reliable high-accuracy rung.
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 : -2.060e-16
feasible               : 1
Beckmann objective     : 386.000008
route time (TSTT/D)    : 92.000000  (analytic UE: 92)
checkpoints certified  : 50 (first gap 3.341e-08, last -2.060e-16)

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), {"algb": 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.

• Segment shifts. Moving flow between a bush’s longest and shortest used segments converges reliably to machine precision with per-origin link storage.

• Where next. the origin-based precursor: oba; the proportionality refinement: tapas; the path-based sibling: gp; the lineage in the model compendium; the full matrix via run_experiment(...) as in demos/demo_quickstart.py.