gp — Gradient projection (Jayakrishnan et al. 1994) on the Braess network

What. Gradient projection works in disaggregate route-flow space: it column-generates a few shortest routes per OD pair and shifts flow off the costlier routes onto the cheapest by a projected Newton step, so each OD’s routes equalize cost directly. Route-based convergence reaches machine precision far faster than link-based Frank–Wolfe, at the cost of storing per-OD route sets.

Why it is in the benchmark. It is the path-based rung of the convergence ladder between conjugate Frank–Wolfe and the bush-based family ([jayakrishnan1994faster]). 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: [jayakrishnan1994faster] (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. `gp` 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,
    GradientProjectionModel,
    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 = GradientProjectionModel()
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            : gp
budget spent     : 50 iterations, 51 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}")

# Route-based gradient projection reaches machine precision on Braess in a handful of
# checkpoints — the payoff of equalizing route costs directly.
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 1.912e-01, 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), {"gp": 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.

• Route space pays. Equalizing per-OD route costs reaches machine precision far faster than link-based Frank–Wolfe — at the cost of storing route sets.

• Where next. the bush-based family it precedes: oba · algb · tapas; the link-based methods: fw · bfw; the lineage in the model compendium; the full matrix via run_experiment(...) as in demos/demo_quickstart.py.