# ADR-020: merchant-nemhauser — Merchant & Nemhauser (1978) exit-function SO-DTA

**Status:** accepted (implemented)
**Date:** 2026-07-10
**Deciders:** analytical-DTA track — the first network DTA model
**File:** `docs/design/adr-020-merchant-nemhauser.md`

## Context

Merchant & Nemhauser (1978) is the first dynamic traffic assignment model of any
kind: a discrete-time, single-destination, SYSTEM-OPTIMAL program that routes
time-varying node demands `d_j(t)` through links whose per-period outflow is
governed by exit functions `g_a(x_a)` of the start-of-period occupancy — congestion
endogenized two decades before the CTM. It is a network-wide *optimization*
paradigm (the decision is the whole inflow/routing plan), distinct from the repo's
route-choice equilibria, the `dnl/` loading kernels, and the `bottleneck/`
departure-time equilibrium — so it gets its own parallel module `src/tabench/dta/`.

## Decision

1. **A parallel module `src/tabench/dta/`** touching no road/DNL/transit/bottleneck
   code (golden Braess hash `cf00f411…` re-asserted in the tests).
   `SODTAScenario` (`scenario.py`) is frozen and content-hashed under a
   `"tabench-dta-scenario-v1;"` domain prefix: nodes, one absorbing destination,
   links, per-link piecewise-linear concave exit functions (pointwise min of
   affine pieces; a mandatory `(slope <= 1, intercept 0)` piece enforces the
   standing M-N assumptions `g(0) = 0` and `g(x) <= x`; slopes `>= 0` keep only
   the nondecreasing branch, exactly as M-N assumed), a `(T, n_nodes)` demand
   table, and per-link cost weights `w_a > 0`.

2. **The canonical program is the Carey (1987) relaxation** (`solve.py`):
   explicit exit variables with `e_a(t) <= g_a(x_a(t))` instead of M-N's equality
   `e = g(x)`. The equality form is nonconvex (Carey 1992); the relaxation is the
   standard convex reading, under which piecewise-linear `g` and linear costs make
   the whole program an LP — one `e - s*x <= c` row per affine piece. Slack in the
   bound is deliberate *holding back* (ramp metering), legitimate and sometimes
   strictly optimal SO behaviour (see anchor B). Time semantics (cross-verified,
   see Sourcing): `x_a(t)` is the start-of-period occupancy; inflow during `t`
   joins the state at `t+1` (cannot exit during `t`); exits of period `t` feed
   downstream inflows of period `t` (same-period hand-off); the destination
   absorbs. Two benchmark conventions close the program: the network starts empty
   (`x(0) = 0`), and **terminal clearance `x(T) = 0`** — without it "total cost"
   is ill-posed (flow can strand more cheaply than delivering); an infeasible LP
   therefore *means* the horizon is too short. `solve_so_dta` solves the LP
   (HiGHS) and emits a `DTATrajectory` — inflows/exits/occupancies plus the LP
   dual vectors in the documented canonical row order.

3. **P1 certificate** (`metrics/dta_gaps.py`, `SODTAEvaluator`). From
   `(scenario, emitted trajectory)` alone the harness recomputes every gate:
   conservation `x(t+1) = x(t) + u(t) - e(t)`, per-period node balance
   `sum u_out = d + sum e_in`, the exit bound `e <= g(x)` with `g` re-evaluated
   from the scenario's pieces, empty start, nonnegativity, and terminal clearance
   (stranded flow is CENSORED). Scored: recomputed `total_cost` and
   `so_optimality_gap = (total_cost - Z*)/max(1, |Z*|)` against a harness-resolved
   canonical-LP optimum `Z*` (the `TransitEvaluator` LP-optimum pattern). If the
   trajectory carries a dual certificate the harness ADDITIONALLY verifies global
   optimality by pure arithmetic — `y_ub <= 0`, reduced costs
   `c - A_eq'y_eq - A_ub'y_ub >= 0`, and the duality gap against the RECOMPUTED
   primal cost (`dual_gap`, `dual_infeasibility`; weak duality makes a passing
   certificate a proof, and a forged one is reported, never believed).
   `exit_slack_max` reports holding-back as a non-gating Tier-B diagnostic.

## Analytic anchors (machine-verified — `test_dta_mn.py`)

- **Anchor A, `mn_parallel_scenario` (capacity metering):** 6 vehicles at `t=0`
  choose between a fast capacitated link (`g = min(x, 2)`, 1 period) and a slow
  uncapacitated 2-link route (2 periods); T=5, unit weights. SO = **10**
  vehicle-periods by an aggregate earliest-arrival bound (`E(0)=0`, `E(1)<=2`,
  `E(tau)<=6` gives cost `>= 30-24 = 10`; achieved by any split sending 2–4
  vehicles down the fast route). Every optimum exits the fast link at its
  capacity bound in period 1. The all-on-fast plan costs 12 and certifies
  `gap = 0.2`.
- **Anchor B, `mn_metering_scenario` (holding back strictly optimal):** series
  `O -A-> M -B-> D`, `g_A = min(x,2)` at weight 1, `g_B = min(x,1)` at weight 2,
  4 vehicles, T=7. Relaxed SO = **18**, and EVERY optimum meters A at rate 1
  while `g_A(x_A(1)) = 2` — strict slack in the exit bound; the naive M-N
  equality dynamics are decision-free here and cost **22**. (The strict gap
  needs the unequal weights: with uniform weights this instance ties at 14 —
  consistent with the literature's account of holding back.) Both anchors carry
  exact LP-duality certificates (verified to zero residual in the tests, and to
  exact rational arithmetic during research).
- Censoring: wrong hash, teleported vehicles, node imbalance, exit-bound
  violations, stranded flow, and negative flows are all censored; forged dual
  certificates are reported with large `dual_gap`/`dual_infeasibility` while the
  untouched primal still certifies.

## Alternatives considered

- **Implementing the M-N equality form with a local NLP solver:** rejected — the
  equality form is nonconvex (Carey 1992), a local KKT point carries no global
  certificate, and the benchmark's P1 discipline wants machine-checkable
  optimality. The Carey relaxation is the field's standard convex reading and
  admits the LP-duality proof.
- **Reusing the `dnl/` stack:** rejected — exit-function dynamics (outflow a
  function of total occupancy, uncapacitated inflow, no spillback) are a
  different physics from the S/R kinematic-wave interface; forcing them into
  `LinkModel` would misrepresent both. The CTM connection is historical, not
  structural: with cells sized to one-period free-flow, M-N's dynamics restricted
  to the sending branch coincide with an optimization CTM (Carey & Watling 2012),
  which is exactly the `lp-so-dta` (Ziliaskopoulos 2000) sprint — a separate
  model.
- **Terminal clearance as a certifier gate only (not an LP constraint):**
  rejected — then the reference `Z*` could strand flow (cheaper than delivering
  near the horizon), and a delivering trajectory would be measured against an
  incomparable bound.

## Adversarial review

Three independent attack lenses, each executing code against the module. What
survived: formulation fidelity (the canonical LP matrices equal hand-written
ones on tiny instances; 40/40 differential agreement with an independently
written LP; time semantics exact — no instantaneous traversal, k-link chains
need exactly k periods), both anchors' strongest claims re-proven independently
(SO=10 with `E(1)=2` forced in EVERY optimum; SO=18 with strict holding back in
EVERY optimum via optimal-face probing; equality form 22; uniform-weight tie
14), and the dual-certificate machinery (forgery is mathematically blocked —
the maximum dual objective over the evaluator's exact feasibility set equals
`Z*`, verified by solving that LP; HiGHS marginals pass at ~1e-15 over 25
random instances with zero false-censors; NaN/inf/wrong-shape forgeries all
rejected). What broke, all CONFIRMED with repros and fixed + regression-pinned:

- **CRITICAL false-accept:** the per-cell tolerance `eps = tol*max(1, demand.sum())`
  let ~eps-sized residuals accumulate over the `T*(links+nodes)` cells into a
  material teleport — a cheating trajectory certified `feasible=1` with
  `so_optimality_gap = -9.9e-4` while ~496 of 1e6 vehicles vanished. Fixed with
  two-scale gates (per-cell residuals at the local `tol*max(1, demand.max())`
  scale AND each violation family's absolute sum capped by the aggregate mass
  budget `tol*max(1, demand.sum())`), a delivery gate, and the weak-duality
  backstop: any cost undercutting the harness's own `Z*` beyond `tol` is
  CENSORED (no feasible plan can beat `Z*`, so undercutting proves infeasibility).
- **MAJOR:** negative-occupancy cost credit — shifting an honest optimum's
  occupancies down by `0.99*eps` kept `feasible=1` while scoring below `Z*` on
  the shipped anchor. Fixed: cost is computed on occupancies clamped at zero
  (plus the aggregate/undercut gates above).
- **MAJOR:** `certify()` raised on a gate-passing trajectory whenever the
  scenario's LP was unsolvable, violating the only-wrong-shapes-raise contract.
  Fixed: `Z*` resolves eagerly in `__init__`, so an unclearable scenario is a
  configuration error at construction, never a crash on model output.
- **MINOR:** the validator admitted scenarios that are infeasible for EVERY
  horizon (binding intercept-0 exit slope < 1 decays geometrically and never
  reaches `x(T)=0`). Fixed: the binding intercept-0 piece must have slope
  exactly 1 (`g(x)=x` near empty — Carey & Watling's coordinated
  discretization; longer free-flow times are link chains).
- **MINOR:** the "frozen" scenario's arrays were mutable in place, silently
  desyncing the content hash from an evaluator's cached `Z*`. Fixed: arrays are
  copied in and frozen read-only.
- **MINOR:** `max(1, |Z*|)` normalization reported absolute (not relative) gaps
  on small-optimum instances, hiding a 22%-suboptimal plan behind a 4e-3 gap.
  Fixed: both gaps normalize by `Z*` itself (strictly positive by validation).

Known scalability note (accepted, not fixed): `canonical_lp` assembles dense
constraint matrices — fine at anchor scale (~KB) but O((3LT)^2) memory; move to
`scipy.sparse` before shipping large generated families.

## Consequences

The benchmark gains the founding network-DTA model and the `dta/` module the
remaining analytical-DTA sprints (Friesz VI-DUE; Ziliaskopoulos LP SO-DTA on CTM)
will build alongside. All changes are additive (a new module + a new certifier +
tests), so the 605-test suite, every existing hash, and the golden Braess content
hash are byte-untouched.

## Sourcing

Merchant & Nemhauser (1978a) "A Model and an Algorithm for the Dynamic Traffic
Assignment Problems," *Transportation Science* 12(3):183–199,
doi:10.1287/trsc.12.3.183, and (1978b) "Optimality Conditions for a Dynamic
Traffic Assignment Model," same issue 200–207, doi:10.1287/trsc.12.3.200 — both
paywalled, attributed (abstracts read; no page-precise content reproduced). The
formulation, time-indexing semantics, exit-function assumptions, relaxation, and
nonconvexity landscape are cross-verified from >= 2 of these OPEN sources (read):
Carey & Watling (2012) (Program S restatement + M-N/CTM App. A), Carey &
McCartney (2004) (discrete dynamics + exit-function branches), the
Friesz/Kwon/Bernstein handbook chapter (dynamics + node balance), Lafortune et
al. (1993) §2 (uncapacitated links, relaxation reading), and Peeta &
Ziliaskopoulos (2001) §2.1 (relaxation tightness, holding back). Carey (1987)
*Oper. Res.* 35(1):58–69, doi:10.1287/opre.35.1.58 (convex relaxation) and Carey
(1992) *Transp. Res. B* 26(2):127–133, doi:10.1016/0191-2615(92)90003-F
(nonconvexity) are in the verified canon. Both anchors were derived from scratch
for this benchmark (no canonical M-N instance exists) and verified by LP +
exact rational duality certificates.