ADR-021: lp-so-dta — Ziliaskopoulos (2000) LP single-destination SO-DTA on CTM cells

Status: accepted (implemented) Date: 2026-07-10 Deciders: analytical-DTA track — cell-level SO-DTA with finite storage File: docs/design/adr-021-lp-so-dta.md

Context

Ziliaskopoulos (2000) casts single-destination system-optimal DTA as a linear program over cell-transmission dynamics: the CTM’s Godunov flux EQUALITY y = min(x_i, Q_i, Q_j, delta_j (N_j - x_j)) is relaxed to its four linear <= constraints while conservation stays an equality. Against the shipped Merchant-Nemhauser model (ADR-020) the physics is new — finite storage and spillback (exit functions with uncapacitated inflow cannot represent either), inherited from the CTM the repo already ships as dnl/ctm.py. The historical line closes: M-N restricted to the CTM’s sending branch at coordinated discretization is an optimization CTM (Carey & Watling 2012), and this model is that program with the full supply side.

Decision

  1. Same parallel module — src/tabench/dta/cells.py beside the M-N files, touching no existing code (golden Braess hash re-asserted). CellSODTAScenario is frozen, read-only, and content-hashed under a new domain prefix "tabench-dta-cell-scenario-v1;": cells with per-interval capacity Q_i (inf allowed), storage N_i (inf allowed), delta_i = w/v in (0, 1] (the LP analogue of the CTM’s w <= vf gate — with the spillback row it gives x <= N by induction), one absorbing sink, sources with no predecessors, a (T, cells) demand table plus an initial occupancy.

  2. The canonical LP (cell_canonical_lp): variables x_i(t), y_c(t); equalities = initial condition, conservation (demand as exogenous RHS; the sink absorbs), and terminal clearance x_i(T) = 0 for non-sink cells — the ADR-020 benchmark convention layered on the primary (which has no terminal condition; without one “total cost” rewards stranding). Inequalities are the four CTM families in the uniform AGGREGATE form (per-cell summed sending and receiving), which coincides with the per-cell-type constraint lists on Ziliaskopoulos’s network class and is the safe superset in general; rows with infinite bounds are omitted. Objective: sum_{t=0}^{T-1} sum_{i != sink} x_i(t) — total system travel time; source queues are costed, the sink is not. Merge priorities and diverge turning fractions are deliberately ABSENT: the SO program chooses them (a controlled CTM). solve_cell_so_dta (HiGHS) emits a CellTrajectory with the LP dual certificate in the documented canonical row order.

  3. P1 certificate (metrics/dta_gaps.py, CellSODTAEvaluator) inherits the ADR-020 adversarial-review hardening wholesale: two-scale gates (local per-cell eps + aggregate mass budget on each violation family), the x <= N envelope, delivery into the sink, clamped-occupancy cost, an eagerly harness-resolved Z* (unclearable horizon = construction-time error), the weak-duality undercut censor, and pure-arithmetic dual verification. New here: holding_max, a Tier-B diagnostic reporting the largest headroom a queued connector leaves unused — LP “traffic holding” is legitimate optimal-face behaviour for a single destination (a non-holding optimum always exists: the earliest-arrival-flow property, Zheng & Chiu 2011, which is also why the LP relaxation is tight), never an error.

Analytic anchors (machine-verified — test_dta_zil.py)

  • zil_diverge_spillback_scenario: 6 vehicles at source R, a diverge at A between a short route through the one-vehicle bottleneck cell B (Q=1, N=1) and a longer C→D route (Q=2). SO = 26 veh-intervals by the spillback pair lemma y_BS(s) + y_BS(s+1) <= 1 (storage + backward wave, not just capacity) plus earliest-arrival bounds; cell B is jam-full at t=2 in EVERY optimum (the storage row is tight, dual price −1), and relaxing N_B to 2 drops the optimum to 25 — the finite-storage constraint is worth exactly one vehicle-interval. A strict-CTM rollout attains 26 (the LP bound is tight and realizable); the all-long-route plan costs 30 and certifies gap = 4/26; a plan holding one vehicle at the source below ALL four bounds still attains 26 and certifies with holding_max = 1 — holding on the optimal face, exactly as the theory says.

  • zil_corridor_scenario: a control-free corridor whose LP optimum (33) equals the repo’s own CTMLink/NetworkLoader strict-CTM loading exactly — cross-model consistency between the analytical-DTA track and the DNL stack.

  • Censoring: teleports, spillback violations (inflow above delta (N - x) that capacity alone would allow), stranded flow, negative flows, wrong hashes, and ADR-020’s shadow-shift undercut are all censored; forged dual certificates report large dual_gap/dual_infeasibility while the untouched primal still certifies.

Alternatives considered

  • Building on dnl/DynamicScenario instead of a cell scenario: rejected — the LP’s data are per-cell (Q, N, delta) with sources/sinks and free merge/diverge controls; deriving them from link-level LinkDynamics + node models would couple the modules and misstate the model (the LP has no node model — that absence is canonical). The corridor cross-check test pins the correspondence where it exists.

  • Per-cell-type constraint lists (Ziliaskopoulos’s exact typography): the uniform aggregate encoding is used instead — identical on his network class (no cell both merges and diverges), well-defined and conservative in general, and one code path instead of five.

  • Adding merge priorities / FIFO diverge rows: rejected — the SO program chooses the controls; adding them would change the model.

Adversarial review

Three independent attack lenses, each executing code. What survived: the LP matrices equal hand-written ones coefficient-for-coefficient (including the delta < 1 receiving-space rows and demand RHS); the anchor was re-proven by hand AND by an independently written per-connector LP (26; N_B=2 → 25; N_B=1.25 → 25.75, i.e. dJ*/dN = -1 exactly; the storage row tight on the ENTIRE optimal face); the aggregate encoding was shown identical to Ziliaskopoulos’s per-cell-type lists even at an off-class merge+diverge cell (optimum 34 = 34, support functions equal to 1e-14) and strictly tighter than a naive per-connector reading (28, CTM-impossible); 5,584 strict-CTM rollouts across 300 random DAGs never beat the LP bound (zero LP > CTM violations); dual forgery is blocked mathematically (the dual LP’s maximum equals Z*) and empirically (20,000-draw search); the reference solver’s duals were never false-censored (worst residual ~9e-16 over 70+ instances, jitter, and 1e±6 scalings). What broke, all CONFIRMED with repros and fixed + regression-pinned:

  • CRITICAL false-accept: the initial-condition gate had a per-cell eps (scaled by x0.max) but NO aggregate budget — the one gate that missed the ADR-020 two-scale fix. With a 1e6-vehicle source setting eps = 1.0, a cheater deleted whole trickle-source vehicles at t=0, conjured replacements at ghost cells beside the sink (delivery nets out; conservation uses the CLAIMED x[0]), buried the savings as holding to dodge the undercut censor, and certified feasible=1 while hiding 495x tol of optimality gap. Fixed: the initial-condition family now carries the same absolute-sum budget as every other family (plus an aggregate negativity budget for depth).

  • MAJOR false-censor: demand pulses into finite-storage sources put the LP and the certifier in disagreement — the receiving-space rows exist only for connector-fed cells, so the LP (correctly, per its own rules) overfills the source while the certifier’s x <= N envelope censors EVERY mass-conserving trajectory, including the solver’s own optimum (18/30 such fuzz scenarios). Fixed at the root: validation now requires infinite storage on demand-loaded cells, exactly as the docstring always claimed (x0 <= N loading stays legal — occupancy is non-increasing at a source).

  • MINOR scale-blind dual reporting: a +1e-12 sign violation on a large-b spillback row moved the “certified” bound by 56x tol while dual_infeasibility read 1e-12. Fixed in BOTH evaluators (ADR-020’s inherits it): y_ub is clipped at 0 before the bound is computed — the clipped vector is sign-feasible by construction, the bound is conservative, and the raw violation is still reported.

  • Two docstring clarifications from NOTE findings: the demand-entry costing convention (injection interval uncosted; x0 costed from t=0) and the “safe superset” phrasing (superset of controlled-CTM trajectories; tighter than per-connector encodings).

Known scalability note (accepted): dense LP assembly — ~1.5 GB at 50 cells x 100 steps, and the evaluator re-solves at construction; fine at anchor scale, move to scipy.sparse before larger families (same boundary as ADR-020).

Consequences

The analytical-DTA track now spans both classical SO-DTA formulations — exit functions (M-N 1978) and cell transmission (Ziliaskopoulos 2000) — under one P1 pattern (canonical LP + eager harness Z* + pure-arithmetic dual certificates). All changes are additive; the 629-test suite and the golden Braess hash are byte-untouched. Dense LP assembly remains the known scalability boundary (ADR-020); move to scipy.sparse before large families.

Sourcing

Ziliaskopoulos (2000) “A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem,” Transportation Science 34(1):37–49, doi:10.1287/trsc.34.1.37.12281 — paywalled, attributed. The LP (variables, objective incl. source queues, the four relaxed CTM families with per-cell-type aggregation, source/sink conventions) is cross-verified from open restatements read in full: arXiv 1708.03759 (Eqs (1), (4)–(9)), arXiv 2112.14389 (Eqs (6)–(9), (13)–(15) — the Beard–Ziliaskopoulos generalized aggregate form), and Peeta & Ziliaskopoulos (2001) §2 (relaxation and holding semantics). CTM correspondence and holding realizability: Daganzo (1994/1995) via the repo’s own dnl/ctm.py (ADR-015); Zheng & Chiu (2011, doi:10.1016/j.trb.2011.03.001, attributed) for the earliest-arrival-flow tightness/non-holding result; Como–Lovisari–Savla (arXiv 1509.06189, read) for controlled realizability. Both anchors were derived from scratch (no canonical instance exists) and verified by LP + zero-residual duality certificates.