fw
|
Frank & Wolfe 1956; LeBlanc, Morlok & Pierskalla 1975 |
LeBlanc introduced Sioux Falls (24-node); only a 1970s-hardware timing, no reproducible flows |
Braess UE (4,2,2,2,4); Sioux Falls best-known flows + objective (below) |
cfw / bfw
|
Mitradjieva & Lindberg 2013 (Transp. Sci. 47(2), full text read) |
Table 3 iterations-to-1e-4: Sioux Falls BFW 124 / CFW 357 / FW 1869; headline “FW ≈ 10× the conjugate variants” |
the ranking is reproduced (in-repo bfw 102 / cfw 219 / fw 1053; fw > 2× cfw,bfw). Absolute counts differ (their gap is objective-bound (UBD−LBD)/LBD, ours is AEC; line-search/tie-break differ) — a ranking/order-of-magnitude pin, not an exact match |
gp
|
Jayakrishnan et al. 1994 (TRR 1443, full text read) |
“10–15 GP iterations vs 300–2000 FW”; but on random grids + a private COMEST Anaheim matrix (not TNTP demand) |
not reproducible; best-known flows + cross-solver agreement. Qualitative “path-based reaches accuracy in far fewer iterations than link-based FW” holds in-repo |
algb
|
Dial 2006 (TR-B 40(10), paywalled/unread; formulas cross-verified vs Boyles TNA §6.4, Nie 2010, TAP-B/TAsK) |
Chicago-region ~40k arcs; “precision unreachable by FW” — no clean table |
best-known flows; reaches tighter gaps than FW at equal budget; cross-solver agreement |
tapas
|
Bar-Gera 2010 (TR-B 44(8-9), paywalled/unread; cross-verified vs Boyles TNA §6.5.3, TAsK, iTAPAS) |
five networks; tight UE gap and entropy-maximizing proportional route flows |
best-known flows; cross-solver agreement; proportionality on an analytic PAS (test_tapas.py) |
so-bfw
|
Beckmann, McGuire & Winsten 1956; Yang & Huang 1998 |
system optimum = UE of the marginal-cost network |
Braess SO: flows (3,3,0,3,3), TSTT 498 (route cost 83), vs UE TSTT 552 (route cost 92) ⇒ Price of Anarchy 552/498 ≈ 1.108 (exact, test_validation.py) |
sue-msa
|
Dial 1971; Fisk 1980; Powell & Sheffi 1982 |
logit SUE convex program + MSA convergence; no cross-implementation-stable flow (θ- and overlap-dependent) |
analytic 2-route logit fixed point f_A = 2.2990959494 at θ=0.5 (recomputed by brentq, test_sue.py) |
sue-probit-msa
|
Sheffi & Powell 1982; Daganzo & Sheffi 1977 |
probit SUE — no closed form; algorithm + MC loading |
analytic/MC 2-route probit f_A ≈ 2.444 at β=0.1, certified by the ADR-003 MC residual (test_probit.py) |
fw-elastic
|
Florian & Nguyen 1974 (paywalled/unread); Gartner 1980; Sheffi 1985 ch.6 / Boyles §9.1 |
elastic-demand equilibrium method |
analytic elastic 2-route: u=5, f_A=3, f_B=2, realized demand 5, flows (3,3,2,2) (recomputed by brentq, test_elastic.py) |
learned-surrogate
|
Rahman & Hasan 2023 (learned-TA line) |
link-flow MAE/correlation (the literature’s metric) |
not a certification target; the harness recomputes the gap — corr 0.63–0.99 across TNTP yet feasible=0 on all (ADR-006, test_learned.py) |
implicit-ue-nn (torch)
|
Liu, Yin, Bai & Grimm 2023 (TR-C 150:104085, paywalled/unread); formulation cross-verified vs the authors’ open hEART 2024 paper + two posters — shipped as a lean variant |
the paper reports link-flow WMAPE on Sioux Falls (their end-to-end NN 1.8%); no cross-implementation-stable flow — validated by analytic anchors + honest held-out direction |
A1 Braess identity: cost head pinned to true BPR (zeroed) ⇒ logit fixed point (4,2,2,2,4), route time 92, gap ~1e-9; A2 IMD/adjoint hypergradient vs central finite differences < 1e-5; A4 feasible=1 at random θ (demand-feasible by construction, v=Δᵀh — the audit the ridge is censored by); θ=0 reduces to the analytic binary-logit split; held-out Sioux Falls (honest, act two of ADR-006): feasible with a finite positive gap that a converged bfw beats by orders (the wall/convergence axis) while at matched sp_calls the direction reverses in the NN’s favor (0.168 vs 0.223 — pinned as a result), and training reduces in-family flow loss but does not improve the held-out gap over plain logit — the identifiability caveat. Three-lens adversarial review (14/14 streak): CONFIRMED + fixed a zero-demand grid-killing crash, a silently-ignored wall_seconds budget (37× overrun), the axis-less headline (the sp-reversal was hiding in it), and a limit-cycling constant-damping fixed point (now adaptive damping, residual ~5e-13 pinned on the cycling instance, Fisk-1980 uniqueness correctly cited) + RNG-clobber and iteration-over-report MINORs; survived: 25-random-head gradient checks, 200-head monotonicity brute force, 110-scenario feasibility fuzz, fairness-gate rename attacks, fresh-venv torch-free simulation, and torch 2.4.1 floor verification (ADR-025, test_implicit_ue.py) |
het-gnn (torch)
|
Liu & Meidani 2024 (TR-C 165:104695, paywalled/unread); formulation cross-verified with zero discrepancies vs arXiv:2310.13193v3 + the NSF PAR accepted manuscript — shipped as a lean variant |
the paper reports link-flow MAE/utilization on TNTP nets (magnitudes unreproducible — its Table-1 demand totals differ from canonical TNTP); validated by analytic anchors + an honest held-out direction |
A2 the paper-faithful raw emission is censored feasible=0 — its conservation loss L_c is the L1 form of the harness node_balance_residual, and its best reported values sit 3–5 orders above the 1e-6·D tolerance (certain censoring, act three of ADR-006) — while a flagged repo-extension route-decode is feasible=1 with a real certified gap; A4 the size-agnostic node-kernel featurization is exactly permutation equivariant (1.1e-16 < 1e-8), where the paper’s |V|+2 OD-row featurization fails (verified 21.5) — the property that lets one trained model transfer across graph sizes; the decode is a projection (Braess UE (4,2,2,2,4) returned; feasible=1 at random θ; monotone, no limit cycle). Held-out Sioux Falls (honest, every axis named): raw wMAPE worse than the ridge (but censored), decoded wMAPE better; implicit-ue-nn 0.168 vs het-gnn 0.259 at matched route sets — recorded as PROVENANCE, not a CI pin: the review PROVED the ordering inverts by ~epoch 130 of training and flips under a 1e-6 weight perturbation on an unpinned-torch CI job (the test asserts only the stable structure); a converged bfw beats both. In-family: training reduces flow loss, and the soft conservation loss lowers the in-family node-balance residual (6.4 vs 11.7) — but that does not transfer to held-out (the identifiability caveat). Three-lens adversarial review (15/15 streak): the fragile-pin MAJOR above; a silent Eq-9 misattribution (the R-Encoder edge weight is a LEARNED generalization of the paper’s fixed feature-sum — now flagged); a stale ablation anchor (7.9/11.6 → 6.4/11.7); and an accidentally-true decode-monotonicity claim (the L-inf residual is non-monotone; the test now pins the L2 objective) — all fixed; survived: 124-scenario decode fuzz, cross-model cache isolation across training orders, 40-permutation equivariance, torch-2.4.1 floor, Anaheim scale (ADR-026, test_het_gnn.py) |
sumo-marouter (eclipse-sumo)
|
Lopez et al. 2018 (IEEE ITSC, DOI 10.1109/ITSC.2018.8569938, a TOOL paper, PDF unread); behavior verified by running SUMO 1.27.1 (marouter/netconvert); vdf lineage is PTV-Validate / VISUM-Cologne per the SUMO source, not the ITSC paper |
the paper reports no marouter assignment numerics to validate against — it is the tool paper for the SUMO package; the row validates ADAPTER fidelity, not the paper’s numbers |
A1 Braess SUE (θ=200) certifies relative_gap ≈ 1.74e-4 = the analytic mapping floor (marouter’s hardcoded linear vdf, forced intercept eps=B·(200/6)/s), flows (3.998,2.002,1.996,2.002,3.998) vs oracle (4,2,2,2,4), node_balance ~7e-14; A2 (mandatory) marouter’s internal traveltime equals the repo BPR at the emitted flows on representable links to ≤1e-6 (~2e-10) — this SEPARATES the mapping floor from solver error, without which the certified gap is uninterpretable; A3 asymmetric two-route UE-approx feasible=1, relative_gap ≈ 5.4e-4 < 1e-3 (θ calibrated on the asymmetric anchor, never symmetric Braess — the theta-tuning trap), a converged bfw orders better (the wall/convergence axis). Honest negative controls: incremental (marouter’s DEFAULT) certifies RG ≈ 0.07 — feasible but non-equilibrium; UE refused (marouter silently falls back to SUE); gawron/lohse refused (all-zero flows). Capability refusals name the field (sue_theta/elastic/power!=1 Sioux Falls); byte-deterministic (no RNG in the SUE path) with the seed pinned on the command line; wall-budget kill RAISES RuntimeError (never a laundered feasible=0); temp-dir hygiene and multi-OD mass conservation pinned. Three-lens adversarial review (16/16 streak): CONFIRMED + fixed a CRITICAL — netconvert’s silent 0.1 m length clamp corrupted zero-intercept eps-edges with FALSE mapping-floor provenance (now a compile READ-BACK verifies every compiled edge against its declaration, and eps-edge lanes are sized to clear the clamp) — plus four MAJORs: the 1-hour OD window silently collapsing to AON past 3600 s path times (window now sized from a worst-path AON bound; ‘No interval matches’ raises), tolls silently dropped (nonzero fixed_cost refuses), the exact-rational flow scale exploding to 1e5+-lane netconvert hangs on 49/50 realistic scenarios (bounded rationalization + a pre-spawn lane-cap refusal), and the wall budget not covering the compile phase (one deadline threads both subprocesses); survived: the vdf tables re-fit by measurement, both anchor floors independently re-derived, command-injection immunity, env hardening, zero-zombie process teardown, and fresh-venv core/CI simulations (ADR-027, test_sumo_marouter.py) |
dtalite-tap (DTALite)
|
Zhou & Taylor 2014 (Cogent Engineering 1(1):961345, DOI 10.1080/23311916.2014.961345, CC-BY, read in full); behavior verified by running the PyPI DTALite 0.8.1 wheel in-tree; the wheel’s assignment() is a Bar-Gera FW.zip-derived static FW TAPLite loop, not the paper’s mesoscopic queue DUE (that is the separate simulation() entry) |
the 2014 paper describes a mesoscopic simulator with no BPR and no equilibrium benchmark numerics — a TOOL-paper anchor for the software lineage; the row validates ADAPTER + engine fidelity, never the paper’s numbers |
The second external engine, and the first with an IDENTITY compile map: the engine’s per-link vdf_fftt/vdf_alpha/vdf_beta maps the repo BPR t = fft·(1 + b·(v/cap)^power) exactly under lanes=1 (the measured lanes² trap), a 1-h period, vdf_plf=1, and lowercase columns (case-sensitive) carrying the repo values verbatim — so BPR power=4 encodes directly (no power!=1 refusal, unlike marouter). A1 Braess (the fft=1e-6/alpha=1e7 sentinels survive the parse) feasible=1, node_balance=0, certified relative_gap ≈ 1.18e-2 at 100 iters frozen from ~iter 40 (the engine’s Armijo line-search stall — the honest ceiling, the wheel-engine-as-shipped, NOT a mapping floor), golden Braess hash cf00f411… byte-identical; A2 (mandatory) the engine’s own travel_time equals the repo BPR at the emitted flows on every link (the identity map’s payoff — no mapping floor to separate) to max relative ~7e-6 (Braess) / ~2e-5 (Sioux Falls power-4, the engine’s 4-decimal column), so the certified gap is pure FW truncation; A3 two-route deterministic UE feasible=1, relative_gap = 0.0 (exact UE f_A=2.5, no theta calibration — contrast marouter); A4 the Sioux Falls power-4 marquee (marouter-impossible) feasible=1, all 76 links matched, relative_gap ≈ 5.0e-3 frozen from ~iter 100, flow NRMSE 1.6% vs best-known — the first external engine on the power-4 ladder; a converged bfw beats the line-search floor by orders (the wall/convergence axis). Negative controls: iterations=1 runs the pure AON (0 FW line searches — measured number_of_iterations=N runs N−1 iterations, output labeled iteration_no=N, N=0 is accessibility mode/empty so the floor is 1) certifying feasible=1 with a worse gap (Braess RG 1.9e-1) and RG(1) > RG(100) (the dial live, compared at iteration 1 — the gap freezes on the plateau); byte-determinism (deterministic, seedable=False — no seed to pin). The subprocess wrapper is mandatory (the engine’s ExitMessage does getchar()+exit() in-process — a bad input would hang on open stdin or kill the host; a second assignment() call in one process doubles the flows), run cwd=fresh tempdir, stdin=DEVNULL, OMP_NUM_THREADS=1 (default all-cores OpenMP is pure spin: Sioux Falls 8.5 s → 0.1 s), one wall deadline (a tiny budget RAISES RuntimeError). returncode==0 is never trusted (the engine exits 0 on missing files/dropped links/zone≠node): a read-back verifies every echoed VDF parameter equals the declared value (float32/4-decimal) and every repo link is matched once. The module never imports DTALite at scope (banner + in-host OpenMP load) — find_spec guard, import tabench prints nothing, and blocking DTALite unregisters the model. Refusals name the field: tolls (unvalidated vot conversion, negative toll kills the host), sue_theta/elastic/combined/br/side-cap/link-interaction/multiclass, capacity≤1e-4, an sp_calls-only budget (sp_calls disclosed 0). The engine’s self-gap is (TSTT−SPTT)/SPTT, not the repo (TSTT−SPTT)/TSTT — recorded as provenance, never gated. Three-lens adversarial review (1 CRITICAL + 3 MAJOR + MINORs, all fixed + regression-pinned): CRITICAL — an ungrouped link.csv corrupts the engine’s FirstLinkFrom adjacency (permuted Braess certified feasible=1 at WRONG flows RG 0.208; permuted Sioux Falls = INFINITE LOOP that under an iterations-only budget hangs solve() forever) → the adapter now writes links SORTED by (from,to) (permutation-invariant, pinned); MAJORs — the engine clamps capacity at fmax(0.1,cap) in the cost law only (a cap in (1e-4,0.1) equilibrates under a different BPR with a passing echo read-back, A2 rel 0.93) → refuse cap<0.1 naming the clamp; the ~1e7 BIG-M cost ceiling silently ZEROES an over-ceiling OD (single link cap=100 pow=4: demand 9000→9000, 10000→0.0) → a per-origin MASS GATE raises (through-flow only adds, so a deficit is always an engine drop); a corrupt-but-parseable output raised a raw ValueError escaping solve() and colliding with the refusal channel → every cell + the file read wrapped to the contract RuntimeError (stdout+stderr tails); MINORs — the echo check is vacuous below atol=1e-3 → a runtime A2 cost-match (engine travel_time==repo BPR at emitted flows on every link, rel 1e-3) is now the LIVE gate closing the blind spot AND catching the clamp; the wall deadline now covers the parse phase (a slow parse RAISES); the summary parser commits (iter,gap) together (no torn pair); the zero-demand path emits both self-report keys; the self-gap 1/(1−RG) claim scoped to the converged regime (it can be negative/frozen off it). Survived incl. the first big-net exposure at iterations=500 — Winnipeg (2836 links, powers 0–6.87) feasible=1 RG 1.176e-3 A2 5.2e-4 wall ~7s; Barcelona (2522 links, powers to 16.83) feasible=1 RG 5.48e-4 A2 7.6e-4 wall ~5.2s — both passing the sort/A2/mass gates. 26 tests; PyPI-metadata Apache-2.0 but the source LICENSE is empty (SPDX NOASSERTION), recorded; no engine code vendored, no TNTP data committed (ADR-029, test_dtalite.py) |
spsa-sumo (eclipse-sumo)
|
Balakrishna, Ben-Akiva & Koutsopoulos 2007 (TRR 2003:50–58, DOI 10.3141/2003-07, primary PDF unread); formulation recovered from Balakrishna’s MIT PhD thesis (DSpace 1721.1/35120) read in full — the TRR paper condenses thesis chs. 3+5 — and cross-verified word-for-word vs Lu’s open MIT W-SPSA thesis (1721.1/88395); Spall 1992 attributed via the shipped spsa row |
no reproducible analytic oracle (the TRR case study is an RMSN-reduction on a proprietary DTA simulator); validated by planted-truth recovery through the real marouter loop + certified through the UNCHANGED pinned-bfw certifier |
the first guarded T2 estimator: a SumoSPSAEstimator(SPSAEstimator) whose inner oracle is the shipped sumo-marouter adapter (adr-027), demand-only (the paper’s JOINT demand+supply contribution honestly NOT shipped — a deferred task family; “DTA” is the paper’s setting, marouter is static; counts only, not speeds). Anchors (two-route only, ≤0.23 s/inner solve, never Braess in CI): a pinned-seed clean-count recovery driving obs-count RMSE and demand RMSE ~5× below the stale prior with a LOOSE improves-on-prior bound (never tight cross-platform decimals — the BLAS lesson), certified od_feasible=1, certificate_gap≈0; a poisson negative-control discloses the honest fragility (under noisy 3-period counts at the same seed the count-fit improvement shrinks to ~0.7× and demand RMSE can degrade vs the prior — small-sample noise + the mapping bias, shared by any count-matching estimator here — so the anchor is clean-count-only). marouter exposes no SP count → sp_calls DISCLOSED as 0 via a _sp_cost_per_eval() hook (the fabricated-sp_calls trap) and an sp_calls-only budget refused up front; one wall deadline threads all 2I+1 inner solves → a mid-loop kill RAISES RuntimeError (crash discipline, never feasible=0); adapter-delegated envelope refusals name the field (power≠1, nonzero fixed cost); bit-reproducible given (root_seed, macrorep) with macrorep divergence; demand is box-projected in BOTH thesis steps — evaluation (_project, in the PARENT loop before loss + best-iterate tracking, so emitted==evaluated==in-box: the P1 fix a three-lens review confirmed after catching an eval-time-only clip that emitted an out-of-box OD with a self-report describing a different point) and the iterate step (_project_log, no frozen corner) — via identity hooks leaving the spsa row byte-identical (parent-identity harness: zero drift); the box-binding regression pins emitted ≤ hi_frac×prior and fails under a clip-removal mutation; sparse pinned-certificate checkpointing. The P1 self-vs-certified honesty diff is REFRAMED as the measured simulator-in-the-loop bias (SPSA descends marouter’s mapped/SUE law, the certificate re-assigns under the declared BPR): measured ~7e-4 count-RMSE clean / ~2e-3 poisson — the same ORDER as the ADR-027 mapping floor, NOT a hard bound, and meaningful only when no box projection engaged; additive, golden Braess hash cf00f411… byte-identical (ADR-028, test_spsa_sumo.py) |
odme-dtalite (DTALite)
|
Zhou & Taylor 2014 (Cogent Engineering 1(1):961345, DOI 10.1080/23311916.2014.961345) — the SAME zhou2014dtalite software lineage as dtalite-tap, whose title names “calibration” (ODME is an instance); no new bib entry, the row validates the ADAPTER + engine artifact, never the paper’s numerics |
DTALite’s ODME is a hardcoded-box gradient descent on a bundled .so with no reproducible analytic oracle; validated by planted-truth recovery through the real DTALite assignment()+ODME loop + certified through the UNCHANGED pinned-bfw certifier |
the second guarded T2 estimator and first ODME row: DTALite 0.8.1’s static performODME (fired INSIDE assignment() when settings.csv carries odme_mode=1, the same static TAPLite path dtalite-tap wraps — NOT simulation()) wrapped as a guarded estimator emitting an OD through od_performance.csv and riding the EXISTING pinned-bfw ODCertifier UNCHANGED (the adr-028 zero-certifier-change ideal — zero task/runner/certifier changes). Marquee (siouxfalls power-4, sensors random cov 0.5 / held-out cov 0.2 / stale prior cv 0.3, seed 7, MEASURE-FIRST pilot): certified obs_count_rmse 994.8→365.3 (0.37×) and the ranking heldout_count_rmse 816.5→556.6 (0.68×) over the prior baseline, the ODME descent running 69 gradient iterations (a real improves-on-prior row, never a “0 iterations” no-op; od_rmse 267.4→264.5 barely moves — a count-matcher, Sioux Falls OD not identifiable from these sensors, od_identifiable=0 reported). Disclosed engine envelope (the pinned-0.8.1 identity, marouter-vdf precedent): route_output=1 is REQUIRED (with the lean route_output=0 the ODME route-history reconstruction collapses and inflates the OD +40% — the non-obvious finding the pilot caught, which would otherwise have SHIPPED a degenerate estimator; also folded into the recorded bundle identity); a hardcoded [0.5,1.5]×-(seed,target) recovery box (demand_target_frac a documented one-sided widening dial, a hashed factor); hardcoded penalty weights + an ABSOLUTE tol=1 floor (so the marquee MUST be Sioux-Falls-scale, not Braess, to clear it); link_performance.csv is CORRUPTED under odme_mode=1 so the OD is sourced EXCLUSIVELY from od_performance.csv (structurally never read — OD byte-identical after deleting it; the odme_mode=0 cost-match/mass gates NEVER reused). Anti-laundering holds by construction and is pinned from both sides (the certifier reads only the emitted OD, never DTALite’s rosy self-report — measured self 8 vs certified 365, the engine-in-the-loop bias; a poisoned OD certifies feasible-but-worse). Subprocess discipline verbatim adr-029 (stdin=DEVNULL, OMP_NUM_THREADS=1, tempdir-per-run, returncode never trusted, wall-kill RAISES, byte-deterministic); sp_calls-only budget refused; delegated toll/capacity refusals (power≠1 representable here, unlike marouter). Single-mode demand-only (multiclass ODME deferred); 19 tests (importorskip DTALite, EXACT case); additive, golden Braess hash cf00f411… byte-identical (ADR-042, test_odme_dtalite.py) |
vi-asym
|
Dafermos 1980 (Transp. Sci. 14(1), paywalled/unread); Smith 1979 (TR-B 13(4)); cross-verified vs Boyles TNA non-separable-cost chapter |
an asymmetric-Jacobian equilibrium minimizes no Beckmann potential, so there is no reproducible standard flow — validated by a hand-derived analytic VI anchor |
2-route asymmetric anchor f_A* = (1+(1−c₁₃)D)/(2−c₁₃−c₃₁) = 6/1.3 ≈ 4.6154 (D=10, c₁₃=0.5, c₃₁=0.2), a flow distinct from BOTH the plain-UE split 5.5 and the symmetrized-Beckmann split ≈5.769 — one no potential solver reaches; VI residual harness-recomputed at the asymmetric cost, reducing exactly to FW UE when C=0 (ADR-011, test_vi_asym.py) |
multiclass
|
Dafermos 1972 (Transp. Sci. 6(1), exact Crossref); cross-verified vs Boyles TNA non-separable-cost chapter + an independent multiclass diagonalization |
a multiclass equilibrium is per-class (each class Wardrop-optimal in its coupled cost); asymmetric interaction has no Beckmann potential — validated by hand-derived two-class anchors |
two 2-class two-route anchors [p,q] = [g_cars/2, g_trucks/2] + (a2/4)·M⁻¹[1,1]: symmetric/integrable M=[[.5,.25],[.25,.5]] → cars (2.5,1.5)/trucks (1.5,0.5), aggregate (4,4,2,2); asymmetric/genuine-VI M=[[.5,.5],[0,.5]] → cars (2,2)/trucks (1.75,0.25), aggregate (3.75,3.75,2.25,2.25) — a flow no Beckmann/FW solver reaches, classes routing distinctly; class-summed VI residual harness-recomputed from the emitted per-class flows, per-class conservation audited, aggregate-only flow censored (ADR-013, test_multiclass.py) |
transit-strategy
|
Spiess & Florian 1989 (Transp. Res. B 23(2), exact Crossref); common-lines formula hand-derived + internally consistency-checked |
uncongested frequency-based optimal-strategy assignment is a convex LP with a closed-form common-lines cost — validated by hand-derived anchors, no external oracle needed |
two common-lines anchors: both attractive (f=1/6,t=21),(1/12,18) → C* = (1+1/6·21+1/12·18)/(1/4) = 24 min, split 2:1; threshold (1/6,15),(1/12,40) → line 2 excluded (40 ≥ 21), C* = 21, all on line 1; a multi-leg interchange (u = 39), a deterministic-walk-dominates case, the primal-dual identity Z_emitted = Z* exact, a multi-destination shared-node scenario and a near-zero-frequency parasite arc (both adversarial-review CRITICALs, fixed to a per-destination, LP-minimal-wait w_i = maxₐ vₐ/fₐ certificate that keeps the gap provably ≥ 0; a non-proportional split is scored as suboptimal, only non-conserving flows are censored); the optimality gap (Z_emitted − Z*)/Z* harness-recomputed against the independently-solved LP optimum, in a parallel transit/ module that leaves the road hashes byte-untouched (ADR-014, test_transit.py) |
ctm
|
Daganzo 1994 (TR-B 28(4), paywalled/unread) + 1995 Part II; cross-verified vs Boyles TNA §10.5 + Daganzo’s open ISTTT 1999 restatement |
the CTM is a convergent Godunov discretization of LWR whose inter-cell flux is min(sending, receiving); validated by exact wave speeds / cumulative curves on hand-derived Riemann problems (no distributable benchmark network) |
three analytic anchors on a triangular FD (vf=w=1, kappa=4, cap=2, dt=1), machine-verified: (a) free-flow translation bit-exact at CFL=1 — n_out(t)=n_in(t−L/vf), TSTT=(L/vf)·D=16, zero delay; (b) queue spillback into a 0.5 bottleneck at inflow 1.5 builds a backward shock at the exact Rankine-Hugoniot speed s=(q_A−q_B)/(k_A−k_B)=(1.5−0.5)/(1.5−3.5)=−0.5, reaching full spillback at t=12, with exact bottleneck boundary curves n_in=1.5t, n_out=max(0,0.5(t−4)) and storage k_B·L=3.5·4=14; (c) the congested cells settle at the supply-side root k_B=κ−q_B/w=3.5. The backward-wave envelope (C5) stays non-gating Tier-B because standard CTM’s congested branch (Courant w/vf<1) is provably diffusive (a known scheme property, not a bug); C1–C4/C6 gate clean. First DNL link model, a LinkModel on the adr-010 core, exercised through NetworkLoader (adr-015, test_dnl_ctm.py) |
ltm
|
Yperman 2007 PhD thesis (KU Leuven, open, read) §4.6 eq. 4.31/4.35; Boyles TNA §9.5.2 (open, read) eq. 9.65/9.67 + worked Table 9.6 |
the Newell-Daganzo cumulative-curve method is exact (no interior discretisation), validated by matching CTM on a shared network and the analytic LWR shock |
four machine-verified anchors on a triangular FD: (a) free-flow translation bit-exact (n_out(t)=n_in(t−L/vf), TSTT=16) — identical to CTM (a); (b) the SAME symmetric 0.5-bottleneck as CTM (b) reproduced byte-for-byte (RH shock −0.5, n_out=max(0,0.5(t−4)), storage 14) — a cross-model consistency check; (c) an asymmetric w<vf spillback (vf=2,w=1,κ=3): RH speed −0.25, shock to x=0 at t=18, n_out=max(0,0.5(t−2)), storage k_B·L=2.5·4=10; (d) the LTM advantage — runs on a non-cell-aligned grid (L=3,vf=2,dt=1 → L/vf=1.5) where CTMLink raises, free-flow-translating by the 1.5 lag exactly. Honest scope: the theoretical zero-diffusion edge over CTM does not manifest on these small single-shock anchors (CTM’s O((w/vf)^n_cells) spreading stays below the certificate tolerance, C5 ~0 for both), so the sprint asserts grid flexibility, not an undemonstrable diffusion gap. Sign-convention note: Yperman’s signed w<0 typesets +L/w; this repo’s w>0 uses −L/w (verified vs Boyles R(10)=5). Stateless LinkModel (adr-016, test_dnl_ltm.py) |
node-model
|
Tampère et al. 2011 (TR-B 45(1), paywalled/unread); algorithm restated from Boyles TNA §9.6.2 (“equal priority movements”) + Yperman 2007 thesis Ch. 5, both open, read |
a first-order node model is a pure allocation solver validated by the node axioms (N1–N6 conservation/consistency) + hand-derived merge/diverge closed forms — no external oracle |
machine-verified anchors (test_dnl_tampere_node.py): merge caps=[1,1]→[0.5,0.5], caps=[2,1]→[2/3,1/3] (capacity-proportional); diverge FIFO [[0.6,0.4]] with out-link 2 blocked to 0.4 → φ=0.5 → q=[0.6,0.4] (one of two vehicles held back on both movements — the whole approach throttled); 2×2 with out-link A binding → [[105/37,45/37],[80/37,120/37]], A saturated at 5, rows exactly turn-proportional (N4); N6 invariance (inflating a non-binding sending flow leaves q bit-identical); a 300-case random fuzz all passing assert_node_axioms (N1–N5); and end-to-end merge + diverge DynamicScenarios certified through NetworkLoader+DNLEvaluator (C1 conservation clean, C8 turn fidelity ~0, capacity-proportional bottleneck sharing) that previously raised. Unlocks network loading for ctm/ltm (adr-017) |
godunov
|
Lebacque 1996 (ISTTT 13, demand/supply Godunov formalism); Greenshields 1935 (parabolic FD); Godunov 1959 / LeVeque Finite Volume Methods (exact Riemann flux) — open restatements |
the Godunov scheme is exact for the local Riemann problem of any concave FD; validated by exact wave speeds + convergence to the analytic LWR solution |
machine-verified anchors (test_dnl_godunov.py) on the first non-triangular FD (GreenshieldsFD, parabolic Q(k)=vf·k(1−k/κ), q_max=vf·κ/4, w=vf): FD derived quantities, parabolic demand/supply branches, and majorant soundness Q(k)≤min(vf·k, vf·(κ−k)); the transonic Godunov flux min(demand(3.5),supply(0.5))=q_max=2 (the entropy-correct rarefaction value, not a shock value); a Greenshields loading certified through NetworkLoader+DNLEvaluator (dnl_feasible=1 — the certifier’s triangular-majorant envelopes stay sound for the concave FD, and its vf(1−k/κ)<vf free-flow speed keeps C4 a fortiori); and the distinguishing anchor — the first rarefaction in the suite: a dam-break Riemann problem converging to the analytic self-similar fan k(x,t)=(κ/2)(1−(x−x0)/(vf·t)), L1 error shrinking monotonically 0.128→0.041 over 20→160 cells (first-order Godunov, slowed by the sonic-point sqrt singularity). GodunovLink reuses the (w>vf-hardened) CTMLink cell update — CTM is the triangular special case (adr-018) |
vickrey
|
Vickrey 1969 (AER P&P 59(2), JSTOR 1823678, no DOI); closed form from Boyles TNA Ch. 10 (open) + independent re-derivation + a discrete-event queue sim; Arnott–de Palma–Lindsey 1990 (general α,β,γ, attributed) |
the single-bottleneck departure-time equilibrium is a closed form (equal generalized cost across used departure times) — hand-derived anchors, no external oracle |
machine-verified on the worked instance (N=6000, s=3000, α=1, β=0.5, γ=2, t*=9): C*=βγ/(β+γ)·N/s=0.8, window t1=7.4, t2=9.4 (width N/s=2), peak t_n=8.2, r_early=6000, r_late=1000, max queue 2400, UE total 4800. The UE certifies equilibrium_gap=0 (every used departure time yields exactly C* — the certifier recomputes the point queue n_{k+1}=max(0,n_k+dR_k−s·dt) and generalized cost from the emitted departure curve, not the solver’s provenance), while the SO (uniform metering at s, no queue) certifies a positive gap (it is not a departure-time equilibrium) with total 2400 — price of anarchy =2 for any β,γ, regression-fuzzed over random penalties. A perturbed schedule scores a positive gap; non-conserving/non-monotone/wrong-hash schedules are censored. First departure-time equilibrium, a parallel bottleneck/ module (adr-019, test_bottleneck.py) |
merchant-nemhauser
|
Merchant & Nemhauser 1978a/b (Transp. Sci. 12(3):183–199 + 200–207, paywalled/unread, abstracts read); formulation cross-verified from ≥2 open sources each (read): Carey & Watling 2012, Carey & McCartney 2004, the Friesz/Kwon/Bernstein handbook chapter, Lafortune et al. 1993, Peeta & Ziliaskopoulos 2001; Carey 1987 (convex relaxation) + Carey 1992 (nonconvexity) in the canon |
the original reports no reproducible benchmark instance (formulation + algorithm paper; the exit-function model has no canonical network), so validation is hand-solvable anchors with global-optimality certificates — the canonical program is the Carey-relaxed LP (piecewise-linear concave g, terminal clearance) where LP duality proves optimality |
two hand-derived anchors, machine-verified (test_dta_mn.py): (a) parallel-route metering (fast g=min(x,2) vs slow 2-period route, 6 vehicles): SO = 10 by an aggregate earliest-arrival bound (E(1)≤2), every optimum exits the fast link at capacity in period 1, all-on-fast costs 12 → certified gap=0.2; (b) holding back strictly optimal (series g_A=min(x,2) w=1 → g_B=min(x,1) w=2, 4 vehicles): relaxed SO = 18 with e_A(1)=1 < g_A=2 (strict exit-bound slack at EVERY optimum), the naive M-N equality dynamics cost 22. Both anchors carry LP-duality certificates the evaluator verifies by pure arithmetic to 0 residual (during research also re-verified in exact rational arithmetic); forged duals report large dual_gap/dual_infeasibility while the untouched primal still certifies; teleports/node-imbalance/exit-violations/stranded flow are censored. A three-lens adversarial review (soundness fuzz, independent-LP re-derivation, dual forgery) CONFIRMED formulation fidelity and that dual forgery is mathematically blocked, and caught a CRITICAL aggregate-tolerance teleport (per-cell eps scaled by total demand certified gap=-9.9e-4 with ~496 of 1e6 vehicles vanished), a negative-occupancy shadow-shift undercut, and an unclearable-scenario scoring crash — all fixed (two-scale mass-budget gates + delivery gate + clamped-cost scoring + weak-duality undercut censor + eager Z* + slope-exactly-1 clearance rule + read-only arrays) and regression-pinned. First network DTA model, a parallel dta/ module (adr-020, test_dta_mn.py) |
lp-so-dta
|
Ziliaskopoulos 2000 (Transp. Sci. 34(1):37–49, paywalled/unread); LP form cross-verified from open restatements (read): arXiv 1708.03759 Eqs (1),(4)–(9), arXiv 2112.14389 Eqs (6)–(9),(13)–(15) (Beard–Ziliaskopoulos aggregate form), Peeta & Ziliaskopoulos 2001 §2; Zheng & Chiu 2011 (EAF tightness, attributed); Como–Lovisari–Savla arXiv 1509.06189 (read) |
the paper’s own instances are illustrative; the LP carries a certifiable GLOBAL optimum via duality, so validation is hand-solvable cell anchors + cross-model consistency against the repo’s own CTM |
machine-verified (test_dta_zil.py): diverge/spillback anchor J* = 26 by the N_B = 1 pair lemma y_BS(s)+y_BS(s+1) ≤ 1 + earliest-arrival bounds — cell B jam-full at t=2 in EVERY optimum (storage row tight, dual price −1), N_B = 2 gives exactly 25 (the finite-storage/spillback physics M-N cannot represent); a strict-CTM rollout attains the LP bound (tight, realizable); the all-long-route plan certifies gap = 4/26; a source-holding plan attains 26 with holding_max = 1 (LP holding on the optimal face, per the single-destination EAF theory); corridor cross-check: LP optimum 33 == the repo’s CTMLink/NetworkLoader TSTT exactly. Dual certificates verify to 0 residual; forged duals are reported, never believed; teleports/spillback-violations/stranding/shadow-shift undercuts censored. Its three-lens adversarial review CONFIRMED formulation fidelity (independent per-connector LP re-derivation; aggregate encoding = Ziliaskopoulos’s per-cell-type lists even off his network class, and strictly tighter than naive per-connector; 5584 strict-CTM rollouts never beat the LP bound; dual forgery blocked — the dual LP’s max equals Z*) and CAUGHT a CRITICAL initial-condition teleport (the one gate missing an aggregate budget: 495× tol of gap hidden at feasible=1), a demand-into-finite-storage false-censor of the solver’s own optimum, and scale-blind dual reporting — all fixed (aggregate init/negativity budgets, infinite-storage validation on demand-loaded cells, clipped-y_ub conservative dual bounds in both DTA evaluators) + regression-pinned. Same-module extension of adr-020’s hardened P1 pattern (adr-021, test_dta_zil.py) |
vi-due
|
Friesz et al. 1993 (Oper. Res. 41(1):179–191, paywalled/unread); VI statement + SRDC-DUE conditions + LDM caveats cross-verified from open sources (read): Han–Friesz–Yao arXiv:1211.0898 (GVM instantiation + existence) and arXiv:1211.4621, the Friesz–Kwon–Bernstein handbook chapter, Peeta & Ziliaskopoulos 2001 §2; parallel-route closed form derived from scratch (Arnott–de Palma–Lindsey lineage attributed, deliberately NOT credited to the 1993 formulation paper) |
the 1993 paper is a formulation/existence paper with no reproducible numerics; validation is the exact parallel-bottleneck closed form + an independent complementarity-bisection solve + discrete-event queue simulation + a cross-certifier reduction to the shipped vickrey model |
machine-verified (test_due.py): worked instance C=0.9, split (5250, 750), queue costs (0.7, 0.2), windows [7.4,9.15]/[7.9,8.4], total 5400, max queue 2100, both-used threshold N > α·s₁·(f₂−f₁)/δ = 3750 (at N=3000: route 1 only, C=0.6); equal-f split is capacity-proportional; single-route f=0 reduction == vickrey (same C*, pointwise-equal curves, and the DUE profile certifies at ~1e-13 under the adr-019 BottleneckEvaluator). The DUEEvaluator scores per-traveler level-inverted costs vs a marginal-insertion reference over EVERY route and all times: the all-on-one-route false equilibrium scores exactly gap = 1/3 (used costs equalize at 1.0, idle route inserts at 0.7 — the failure mode a single-route certifier cannot see), the adr-019 burst dump and an SO-metered profile score large gaps, and non-conserving/non-monotone/wrong-hash profiles are censored. Research honesty: naive fixed-point dynamics (Smith swap, raw projection) CYCLE on this non-monotone operator, and a projection ergodic average converges in aggregates while its profile certifies gap 0.48 — the P1 certifier, not the solver, is the arbiter (adr-022). Two-round adversarial review (round 1: numerics; round 2: soundness + formulation re-run after an infra failure, on the fixed code): CONFIRMED a grid-horizon-dependent extension (25.6×), a greedy underflow C=inf, a cancellation split, then a round-2 CRITICAL false-accept (hull-diluted insertion sweep certified due_gap=0.0 for a profile where every traveler improves 20%), a tiny-N −inf false-accept, and an in-domain conditioning failure — all fixed (exact served-curve + exact kink-enumerated reference minimum, censor, constructor conditioning gate) and regression-pinned; survived: greedy vs exact 2^R KKT on 6000 draws, independent event-driven queue simulator on 120 profiles (<1e-9), all 15 anchors re-derived, and the 2200-draw property fuzz re-run post-fix (worst equilibrium |
pm-td-ue / pm-td-so
|
Peeta & Mahmassani 1995 (Ann. Oper. Res. 60:81–113, doi:10.1007/BF02031941) — primary READ IN FULL (all 33 pp, author-page scan; a first for a DTA row); DYNASMART speed–density family cross-verified from the open Mahmassani-school FHWA weather report; the 1995 canon blurb’s “rolling-horizon” descriptor corrected as a misattribution (the paper reserves that for its TR-C 3(1) sibling) |
the paper’s 50-node DYNASMART numerics are engine-bound and irreproducible (node OD matrix, generation seeds, parameter file, and the marginal estimator’s “averaging techniques” unpublished) and the adapter is licensing-deferred (adr-030), so validation is INVARIANT certification on the repo’s OWN CTM/LTM loading (the paper’s architecture — simulation defines the loading map F — with the repo’s kinematic-wave physics substituted for DYNASMART), never a table match |
machine-verified (test_tdta.py): the model emits ONLY its decision variable (TDPathFlows: per-path, per-departure-interval flow), the harness reruns its own per-path loading (a private first link per path + TampereNode merges on an interior-diverge-free topology that keeps per-commodity experienced times exactly decidable) and scores tdue_gap (the experienced-time route-swap residual by FIFO level composition — total experienced time vs the total if every traveler took their OD’s cheapest available path at their own departure time; 0 iff the discrete Wardrop conditions (5a)/(5b) hold, the reference minimum scanning EVERY declared path so the cheap route cannot be hidden) and so_bound_gap ((TSTT − Z*)/Z* against the lp-so-dta LP optimum on the CTM-cell instance derived from the same grid, which provably lower-bounds every CTM loading). Anchors: a single-path corridor whose loaded TSTT equals the ADR-021 zil_corridor optimum 33 EXACTLY through the new loader (the derived cell scenario is byte-identical); a symmetric diamond whose exact TD-UE (50/50) certifies tdue_gap=0, its all-on-one control the hand gap 0.75 (the hidden-cheap-path family); an SO≠UE wedge (the paper’s headline made executable) where the SO split attains the LP bound (so_bound_gap=0, TSTT 23) and beats the UE TSTT (24), all-on-fast worst at 33; a merge for per-commodity attribution; ltm==ctm on the diamond and the aggregate loader passing the shipped dnl_gaps C0–C8 as a free oracle. Fixed departure times give a two-scale demand-match gate that censors all timing gaming (F2/F4); wrong-hash/NaN/negative/retraction-accumulation/stranded-flow emissions censored. The MSA solvers (experienced-time UE, marginal-cost SO via the 3-point quadratic ∂T/∂x fit) are NON-certified — the certifier, not the solver, is the arbiter, and the certified best iterate is emitted (disclosed deviation from the paper’s N(ε)≤Ω stability count). First iterative simulation-based TD route equilibrium; single user class, fixed departures, NOT rolling-horizon; parallel tdta/ module (adr-031, test_tdta.py) |
T2 estimators (vzw-entropy, gls, spiess, spsa, od-congested, od-kalman) |
Van Zuylen & Willumsen 1980; Cascetta 1984; Spiess 1990; Spall 1992; Yang et al. 1992; Davis & Nihan 1993 (read, JSTOR stable/171951) |
OD estimation is underdetermined — no reproducible standard flow |
planted-matrix recovery on synthetic counts + held-out sensor fit; od-congested adds a closed-form θ-weighted anchor (GLS with scalar variances 1/θ, 1/(1−θ)), prior↔count θ-limit consistency, and congested-fixed-point recovery of the equilibrium-consistent truth; od-kalman adds the Davis–Nihan large-population Gaussian limit — a two-route DN cross-link covariance closed form Var(link) = (D²/N)·p_A·p_B (same-route +, cross-route − correlation), the single-sensor DN-GLS closed form g* = (g_pr/w² + p·c/s²)/(1/w² + p²/s²), and the AR(1) effective-sample-size factor τ = (1+ρ)/(1−ρ) recovered from the count series (test_estimation.py, test_dn_kalman.py, ADR-002/ADR-012) |
Dynamic T2 estimators (od-dynamic-sim, od-dynamic-seq) |
Cascetta, Inaudi & Marquis 1993 (Transp. Sci. 27(4):363–373, paywalled, abstract read at INFORMS); within-day formulation cross-verified from ≥2 open sources read in full: Djukic 2014 (TU Delft) eqs 2.3–2.13, Peterson 2007 (LiU) eqs 16–17, Castiglione et al. 2021 (Frontiers), Cipriani et al. 2014 (ETRR) |
within-day dynamic ODME is underdetermined and time-lagged — no reproducible standard; the estimand is the (H, Z, Z) departure-slice profile, and the exogenous free-flow lag map makes the count model exact linear algebra (bfw-free certifier) |
five hand-derived closed-form anchors recomputed in-test (test_od_dynamic.py): an integer-lag reduction to the static gls closed form (simultaneous == sequential), the fractional-lag instance where simultaneous strictly dominates sequential componentwise (128/35, 142/35) vs (16/5, 94/25) against truth (4,6), a pure-math pin with the sequential−simultaneous error-covariance gap exactly rank-1 PSD (eigenvalues {0, 17/220}; a test-local derivation, NOT attributed to the paper, no shipped covariance API), a mean-collapse distinctness witness (not a gls rename), and the two new identifiability edges — cross-slice temporal confounding (held-out sensors share the lag structure → a count-invariant shift fools obs AND held-out counts) and horizon truncation (demand dumped into an unobservable last slice is count-invariant), both gating od_identifiable; the certifier regenerates the full-network lag map from the hashed recipe (map forgery impossible); golden Braess hash + a pinned static-T2 task hash byte-identical. Three-lens adversarial review: CONFIRMED + fixed a MAJOR count-invisible off-support-demand censor gap, a MAJOR prior_var_floor=0 harness hang, and five MINORs (incl. the diagonal-inflated negativity tolerance, fixed for parity in the static ODCertifier, and the sigma_min identifiability floor); survived 1500 time-invariant + 800 time-varying random instances vs independent from-scratch GLS implementations (zero disagreements), a 2M-departure split simulation, and sympy re-derivation of every anchor (adr-023) |
newell-3det
|
Newell 1993 Part I (TR-B 27(4):281–287, paywalled/unread; the two-translation min is Part II’s, DOIs recovered/Crossref-verified but not added to references.json); formulation cross-verified from ≥3 open sources read in full: Boyles TNA §9.4.4 eq. 9.46, Rey–Jin–Ritchie 2019 (TR-C, eScholarship) eqs 7–11, Daganzo VWP-2006-2 (eScholarship) eq. 17 |
Part I is general theory with no estimation numerics — the noisy-task framing is the repo’s own P3 convention; the estimand is the interior cumulative field, and the harness regenerates the clean detector curves (LTM on the corridor) and evaluates the closed-form min at a fixed hashed query grid, so the reference is exact |
the benchmark’s first traffic-state-estimation task, five hand-derived anchors recomputed in-test (test_newell.py): free-flow exactness N(x,t)=N_up(t−x/vf); an asymmetric interior Rankine-Hugoniot shock (vf=2,w=1,κ=3,L=4, inflow 1.0 into a 0.5 meter) whose min-switch is the hand-computed crossing (born at (x=4,t=2), speed −0.25, passing x=2 at t=10 with N=9, post-shock N(2,t)=0.5t+4, reconstructed density k_B=κ−q_B/w=2.5) — with the +(L−x)/w wrong-sign variant machine-caught (switch moves to t=14); LTM==CTM byte-for-byte on the aligned symmetric bottleneck (cross-model truth, the corridor==CTMLink move); a seeded Gaussian-reading noisy card where the isotonic-then-min estimator strictly beats the naive running-max baseline in interior RMSE by a pinned margin (naive 1.093 vs isotonic 0.448) — the acceptance test that the ranked task separates methods and is not a formula evaluation; and a masked-upstream observability edge where the congested branch alone pins the interior EXACTLY where active (error 0 on every congested-active cell; the only discrepancy is x=1 at t∈{12,13}, still free-flow but unobserved, off by exactly 1.0). The ThreeDetectorEvaluator gates the emission-alone validity checks (finite/zero-start/non-negativity/running-max total-retraction, adr-022) while the pairwise Newell envelopes are non-gating Tier-B (the C4-gating/C5-Tier-B split: a legitimate noisy estimate violates them at noise scale, so gating false-censors the honest baseline); the clean level is an oracle row (rankable=0), ranking lives on the noisy levels; truth recipe never reaches the model-visible payload; golden Braess hash byte-identical. Newell’s LOADING content already ships as ltm (adr-016); this ships the INTERIOR minimum principle as a state-estimation task, not a third LinkModel. Three-lens adversarial review: CONFIRMED + fixed three MAJORs (one root cause: masked-window branch-dropping false-censored the honest baselines via C3 non-monotonicity and C0 inf on doubly-masked cells — fixed by the suffix-min tightest monotone upper bound; plus the degenerate-rankable gaussian-sigma=0 card) and five MINORs (infinite-vehicle-scale gate neutering + hash byte-migration collision, apex metering crash, Poisson lam bound, duration-amplified retraction budget, off-grid truth-exactness scoping); survived: independent LWR re-derivation + from-scratch Godunov cross-check on 7 regimes + 200 random instances, all anchors recomputed, no information leak, complete 18-dial hash coverage (adr-024) |