ADR-022: vi-due — Friesz et al. (1993) VI dynamic user equilibrium

Status: accepted (implemented) Date: 2026-07-10 Deciders: analytical-DTA track — the dynamic USER equilibrium (closes the track) File: docs/design/adr-022-vi-due.md

Context

Friesz, Bernstein, Smith, Tobin & Wie (1993) cast the simultaneous route-AND-departure-time (SRDC) dynamic user equilibrium as a variational inequality over path departure-rate profiles: find h* in the volume-feasible set (sum_p int h_p = Q per OD) with <Psi(h*), h - h*> >= 0, where Psi_p(t, h) is the effective delay (traversal plus schedule-delay penalty). At a DUE every USED (route, departure-time) pair carries equal minimal effective delay and unused pairs cost at least as much — the field’s standard DUE definition, first stated in this paper. The VI is loading-agnostic; the 1993 paper’s own link-delay model is FIFO-safe only for affine delays, so the computable-DUE literature instantiates the same VI with the generalized Vickrey point-queue loading (Han, Friesz & Yao 2013 — the standing existence theory). That is exactly the loading this repo already ships (bottleneck/, ADR-019), which makes the faithful, certifiable benchmark unit: the Friesz VI on parallel Vickrey-bottleneck routes — one route with f = 0 reduces literally to the shipped vickrey model, and the route axis adds the simultaneous-choice content the single-bottleneck model lacks.

Decision

  1. Extend the bottleneck/ module (due.py) — the machinery is the departure-time-equilibrium machinery. DUEScenario (frozen, read-only, hashed under "tabench-due-scenario-v1;") is the Vickrey scalars plus per-route (f_r, s_r) arrays. The analytic structure is exposed on the scenario: with delta = beta*gamma/(beta+gamma) each used route runs its own Vickrey equilibrium at the common cost level C, so N_r = s_r (C - alpha f_r)/delta and

    C = (delta*N + alpha * sum_U s_r f_r) / sum_U s_r

    with the used set U found by a greedy sweep in increasing-f order (a route is used iff alpha f_r < C). due_closed_form emits a DUEProfile — per-route cumulative departure curves on one shared grid (the multi-route BottleneckSchedule).

  2. P1 certificate (metrics/due_gaps.py, DUEEvaluator). From (scenario, emitted profile) alone: censor gates (hash, finiteness, grid monotonicity, zero starts, nondecreasing rows, TOTAL-volume conservation — the per-route split is deliberately ungated: the DUE chooses it); per route, shift by f_r, extend the grid until the queue provably clears, simulate the deterministic point queue, and score PER TRAVELER by level inversion of both curves (the ADR-019 lesson, unchanged). The route axis introduces a genuinely new failure mode the single-route certifier cannot see: an all-on-one-route profile equalizes its own used costs while the idle route is strictly cheaper. The reference minimum therefore scans the marginal-insertion cost of every route (used or not) — an infinitesimal deviator joins behind R_r(t) travelers, exiting at max(t + f_r, D_r^{-1}(R_r(t))) — over the profile’s grid UNION a dense harness-chosen sweep of the analytic window UNION {t* - f_r} (a profile cannot hide the cheap region by its choice of grid). Score:

    due_gap = (max used per-traveler cost - min marginal cost anywhere) / C

    0 iff the discretized Friesz DUE conditions hold across BOTH choice dimensions; positive with the incentive to deviate in time OR route. Tier-B: recomputed totals (cost, expected cost, max queue, travel delay).

Analytic anchors (machine-verified — test_due.py)

Worked instance friesz_two_route_scenario (N=6000, routes (f=0.2, s=3000) and (f=0.7, s=1500), alpha=1, beta=0.5, gamma=2, t*=9):

  • C = 0.9; split (5250, 750); queue costs (0.7, 0.2); windows [7.4, 9.15] and [7.9, 8.4]; total cost C*N = 5400; max queue 2100. The closed form certifies due_gap = 0.

  • Both-used threshold: routes 2 is used iff N > alpha*s_1*(f_2 - f_1)/delta = 3750; at N = 3000 only route 1 runs (C = 0.6 < alpha f_2 = 0.7) and still certifies.

  • Equal free-flow times: the split is capacity-proportional, C = delta*N/(s_1+s_2).

  • Single-route f = 0 reduction: identical C* to the shipped vickrey model, the emitted curve matches ue_closed_form pointwise, and the DUE profile certifies equilibrium_gap ~ 1e-13 under the ADR-019 BottleneckEvaluator — a cross-certifier consistency pin.

  • False equilibria rejected: all-on-one-route scores exactly (1.0 - 0.7)/0.9 = 1/3 (the marginal-insertion scan); the ADR-019 burst-dump and an SO-style metered profile score large positive gaps; non-conserving/non-monotone/wrong-hash profiles are censored.

During research the closed form was additionally verified by an independent complementarity-bisection solve (scalar monotone fixed point on C — machine precision agreement) and by discrete-event queue simulation; naive fixed-point dynamics (Smith swap, raw projection) were confirmed to CYCLE on this operator (it is non-monotone — the known instability of departure-time adjustment), and a projection iterate’s ergodic average converges in aggregates while its profile is NOT an equilibrium (repo-certified gap 0.48) — exactly why the P1 certifier, not the solver’s claim, is the arbiter.

Alternatives considered

  • A general-network VI-DUE with grid-based fixed-point dynamics: rejected for this sprint — the effective-delay operator is non-monotone and the naive dynamics demonstrably cycle; shipping a solver whose convergence cannot be certified would put the benchmark’s weight on luck. The parallel-bottleneck class has the exact closed form, full existence theory under GVM loading, and machine-checkable certificates; a general-network extension belongs with a route-and-time column-generation sprint of its own.

  • The 1993 link-delay-model loading: rejected — FIFO-safe only for affine delays, uncapacitated exits, and superseded by the GVM instantiation in the computable-DUE literature; the VI itself is loading-agnostic, so the GVM choice is faithful to the formulation.

  • Gating the per-route split: rejected — the DUE chooses the split; identical routes make it non-unique. Only total volume is conservation.

Adversarial review

Three independent attack lenses were launched; in round 1 two of them (soundness, formulation) died on an infrastructure session limit and ONLY the numerics lens completed — so the two dead lenses were re-run as a fresh round 2 against the round-1-fixed code. Full coverage was reached across the two rounds; every finding below is CONFIRMED by an executed repro and every fix is regression-pinned in test_due.py.

Round 1 (numerics lens). (a) MAJOR: the certifier extended the served curve past the horizon with a 65-point interpolated linspace, bending the queue-clearing kink — the same piecewise-linear plan scored up to 25.6× differently depending on where its emitted grid ended. Fixed by reconstructing the point-queue served curve EXACTLY: within each segment the arrival rate is constant, so the queue either serves at s_r or tracks the arrival curve, with at most one interior queue-empties kink — computed analytically and inserted, plus the exact post-horizon clearing chord. (b) MINOR: the greedy used-set broke at k = 1 when alpha*f_1 was so large that the queue term rounded away (C = inf); the cheapest route is now always used. (c) MINOR: N_r = s(C - alpha*f)/delta cancelled catastrophically at large f (the closed form missed its own conservation gate); replaced by the difference form Cq_r = (delta*N + alpha*sum s_i(f_i - f_r))/sum s_i plus exact renormalization. (d) MINOR: degeneracy floors alpha - beta >= 1e-9*alpha, gamma <= 1e9*beta added as documented domain bounds. NOTEs: the per-step monotonicity gate was replaced by a running-max total-retraction gate (the DTA eps-accumulation family). Survived: greedy vs 2^R brute force on 12k draws; closed-form exactness ~2.3e-10 across grid densities; cross-certifier agreement with the adr-019 evaluator.

Round 2 (soundness + formulation lenses, on the fixed code). Both lenses independently converged on the same CRITICAL: the marginal-insertion reference scan swept linspace(min(span_lo, t[0]), max(span_hi, t[-1]), 4001) — a fixed COUNT over a hull the solver’s own grid stretches — and the true cheap-insertion times (the queue-drain dip, where waiting for a residual queue to vanish is cheap) are kinks that were never candidates. Executed repros: a truncated-isocost two-route profile in which EVERY traveler pays exactly 2.0 while deviating into the hidden drain window costs 1.6 (a 20% improvement) certified due_gap = 0.0 once one flat pad point at t = 1e6 diluted the sweep; a single-ramp profile with true gap 0.765 certified −0.0001. FIXED by making min_ref EXACT: the marginal-insertion cost is piecewise linear in the insertion time with enumerable kinks — the profile’s grid, the pullbacks A^{-1} of every served-curve kink level, the pullback of level S(t*), and the queue-vanishing zeros of A(t) - S(t + f_r) — all enumerated per route, with the dense sweep demoted to belt-and-braces over the FIXED analytic window. The repros now score 0.2027 and 0.7653, invariant under pads to 1e7. Also confirmed and fixed: MAJOR — scenarios with N <= tol skipped every route and certified arbitrary conserving garbage at due_gap = -inf (now censored explicitly); MAJOR — in-domain instances with (beta+gamma)*ulp(t*) comparable to C score the honest closed form at gap up to 1.0 because no float64 profile can resolve the equilibrium (98/1100 fuzz draws pre-fix; now rejected at construction by a conditioning gate (beta+gamma)*eps_mach*(|t*|+window) <= 1e-9*C); MINOR — the level sampling excluded the first/last traveler where the cost supremum is often attained (boundary levels eps/n_r - eps now sampled); NOTEs — Tier-B totals now use a grid-size-independent level count plus the switch/t*-crossing levels. Survived round 2: greedy vs exact 2^R KKT enumeration on 6000 draws (zero structural disagreements, near-ties at 1e-13, thresholds at ±1e-15); an independent event-driven point-queue simulator matching the reconstructed served curves on 120 profiles to <1e-9; all 15 numeric anchors re-derived independently; gate-boundary float-dirt probes; the round-1 fixes themselves. Post-fix, the reviewers’ 2200-draw property fuzz re-run: every accepted draw certifies its closed form at worst |due_gap| = 8.4e-9 (pre-fix: up to 1.0), zero false-censors, zero negative gaps, zero crashes.

Consequences

The analytical-DTA track is complete: departure-time UE (vickrey), SO-DTA in both classical formulations (merchant-nemhauser, lp-so-dta), and the dynamic USER equilibrium (vi-due) — Wardrop’s two principles, dynamic, under one P1 pattern. All changes are additive; the 652-test suite and the golden Braess hash are byte-untouched.

Sourcing

Friesz, Bernstein, Smith, Tobin & Wie (1993) “A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem,” Operations Research 41(1):179–191, doi:10.1287/opre.41.1.179 — paywalled, attributed. The VI statement, SRDC-DUE conditions, effective-delay operator, and the link-delay-model caveats are cross-verified from open sources read in full: Han, Friesz & Yao (arXiv:1211.0898 — the GVM instantiation and existence theory; also arXiv:1211.4621), the Friesz–Kwon–Bernstein handbook chapter (nested exit-time composition, LDM history), and Peeta & Ziliaskopoulos (2001) §2 (the 1993 attribution of the DUE conditions). The parallel-route closed form is standard bottleneck-theory material (Arnott–de Palma–Lindsey lineage, attributed), derived from scratch here from the isocost conditions and machine-verified by LP-free bisection + discrete-event simulation; it is deliberately NOT attributed to the 1993 paper, which is a formulation/existence paper with no closed form. No page-precise quotes reproduced.