# ADR-009 — Side-constrained UE: hard link capacities with a link-visible feasibility certificate **Status:** accepted (shipped in v1) **File:** `docs/design/adr-009-side-constrained-ue.md` ## Context Ordinary UE lets a link's flow grow without bound (the BPR cost just rises). **Side-constrained traffic assignment** (Larsson & Patriksson 1995) adds **hard link-capacity constraints** `v_a <= u_a` — physical throughput limits — to the Beckmann program: ``` min_x sum_a integral_0^{v_a} t_a(w) dw s.t. demand feasibility, v_a <= u_a for all a. ``` Its KKT conditions are a Wardrop equilibrium on the capacity-**augmented** cost ``` c_a(v) = t_a(v_a) + beta_a, beta_a >= 0, beta_a (u_a - v_a) = 0, ``` where `beta_a` is a multiplier that is zero off the binding set and, where a capacity binds, is the **queueing delay / congestion toll** that stops travelers piling onto the physically-cheap but full link (Larsson & Patriksson 1999: "the Lagrange multipliers … are the link tolls the travellers are willing to pay … the delays in steady-state link queues"). When no capacity binds, SC-TAP is literally the unconstrained program, so it reduces **exactly** to plain UE. ## Sourcing Larsson & Patriksson (1995, *TR-B* 29(6):433-455) is paywalled and **attributed unread**; the augmented-cost equilibrium, the multiplier-as-toll reading, and the augmented-Lagrangian form are cross-verified from the 1999 companion, Nie-Zhang-Lee (2004), and standard augmented-Lagrangian theory (Bertsekas 1982). The analytic anchor numbers are **derived here**, hand-checked, and not quoted from the primary. ## Decision 1 — Per-link capacities as content-hashed scenario data `Scenario.side_capacities: np.ndarray | None` (`core/scenario.py`) carries the hard caps `u_a` (length `n_links`). Validated finite and `> 0`; **content-hashed only when set** (appended last, golden Braess hash preserved); **mutually exclusive** with `sue_theta` / `elastic_demand` / `combined_demand` / `br_epsilon`. A change in any `u_a` is a different benchmark instance. ## Decision 2 — Method of multipliers wrapping Frank-Wolfe `sc-tap` (`SideConstrainedModel`, paradigm `static_sc_ue`) solves it by the augmented-Lagrangian method of multipliers. The inner problem, for fixed `(beta, rho)`, is an ordinary UE with the modified — still non-decreasing — link cost `t~_a(v) = t_a(v_a) + max{0, beta_a + rho(v_a-u_a)}`, solved by Frank-Wolfe with an exact Brent line search on the augmented objective. The outer loop updates `beta_a <- max{0, beta_a + rho(v_a - u_a)}` and grows `rho` when the worst violation stops shrinking. At the fixed point the constraints hold exactly and the recovered `beta_a` is the true multiplier (unlike a fixed large-penalty solve, which is only feasible as `rho -> infinity`). **Robustness (pre-emptive fuzz).** An **infeasible** instance — a capacity below a cut link's *forced* flow, where no SC solution exists — would otherwise drive `beta`/`rho` to overflow (a crash). We cap `rho <= 1e10` and `beta <= 1e8` (both far above any real queueing toll for the benchmark's cost scales) and break on any non-finite cost or shortest-path failure, so an infeasible instance stops gracefully with the constraint reported violated rather than crashing. ## Decision 3 — A link-visible capacity-feasibility certificate The SC-specific scored quantity is **capacity feasibility**, link-visible and checked **per link** to a tight *relative* tolerance (unlike the multipliers, which are duals). A hard cap is a per-link quantity, so the tolerance is relative to each link's own capacity — scaling it by total demand (as the demand-feasibility audit does) would let a fixed absolute overload certify on a high-demand network (an adversarial-review finding, corrected before this commit): ``` max_capacity_violation = max_a (v_a - u_a)+ # absolute, for diagnosis rel_overload = max_a (v_a - u_a)+ / u_a # per-link relative sc_capacity_feasible = 1.0 iff rel_overload <= feasibility_tol ``` The **raw-cost relative gap stays positive** at a correct SC equilibrium (binding links carry flow that would prefer to grow), so it is reported for provenance but is **not** the acceptance criterion — the acceptance criterion is capacity feasibility. The recovered `beta_a` and the augmented-cost gap are model self-reports; a fully harness-recomputed augmented-cost equilibrium gap (recovering `beta` as shadow prices on the binding set by a small convex program) is a documented enhancement. This is honest: the scored certificate certifies *feasibility*, not the full equilibrium; equilibrium is validated by the analytic anchor and the no-binding UE reduction. ## Consequences - **New:** `Scenario.side_capacities`; paradigm `static_sc_ue`; the `sc-tap` model; `sc_capacity_feasible` + `max_capacity_violation` scored metrics; `sc_two_route_scenario` anchor (no-binding → exact UE `(5.5,5.5,4.5,4.5)`; cap 4 → `(4,4,6,6)`, recovered `beta = 3 = 1 + D - 2*cap`); `tabench run --scenario sc-tworoute`. - **Validation:** the anchor + monotone-tightening sweep; the exact no-binding UE reduction (matches the shipped FW solver); a fuzz confirming **zero crashes on solvable instances** and, by a min-cut classification, that sc-tap converges to capacity-feasibility on **100% of feasible instances** and only reports infeasibility on genuinely-infeasible ones. - **Unchanged:** every prior scenario hash (golden Braess preserved); all other certificate paths; all prior models and tests. - **Deferred:** the harness-recomputed augmented-cost equilibrium gap (shadow-price recovery); per-class capacities; explicit infeasibility *reporting* (beyond `sc_capacity_feasible = 0`).