# ADR-007 — Combined trip distribution + assignment (Evans 1976): a P1-pure certificate

**Status:** accepted (shipped in v1)
**File:** `docs/design/adr-007-combined-distribution-assignment.md`

## Context

Every fixed-demand task fixes the whole OD matrix; the elastic task (ADR-005) makes each
pair's *total* demand a pointwise function of its own cost. **Combined trip distribution +
assignment** (Evans 1976) goes one step further: only the trip-end margins are fixed — the
productions `O_i` and attractions `D_j` — and the *entire* OD matrix `d_ij` is endogenous,
distributed across pairs by a doubly-constrained **gravity** model at the equilibrium travel
costs. Distribution and assignment, historically two separately-iterated models, become one
convex program (Evans 1976; Sheffi, *Urban Transportation Networks* 1985 ch. 6; Boyles,
Lownes & Unnikrishnan, *Transportation Network Analysis* §6):

```
min_{x,d}  Σ_a ∫_0^{x_a} t_a(w) dw  +  (1/β) Σ_ij d_ij (ln d_ij − 1)
s.t.  Σ_j d_ij = O_i,   Σ_i d_ij = D_j,   d ≥ 0,   x = assign(d)
```

Its stationarity conditions give **both** the doubly-constrained gravity
`d_ij = A_i B_j exp(−β u_ij)` (`u_ij` = equilibrium OD cost, `A/B` = Furness balancing
factors) **and** Wardrop route equilibrium of `d`. This is a genuinely new problem class,
and — like elastic demand — it collides with the harness's fixed-OD assumptions. ADR-005
anticipated it ("Deferred: a combined distribution–assignment task (Evans 1976) that reuses
this machinery"); this ADR is that reuse.

## Sourcing (dual-verified against open textbooks)

The primary — **Evans (1976)**, *Derivation and analysis of some models for combining trip
distribution and assignment*, Transportation Research 10(1), DOI
`10.1016/0041-1647(76)90100-3` (canon key `evans1976derivation`, tier 1) — is paywalled; its
abstract and the "Evans algorithm" convergence result are attributed unread. The **formulas
implemented here** (the combined objective, the partial-linearization algorithm, the
doubly-constrained gravity subproblem, the Furness/IPF balancing) were recovered from two
primary-accessible textbooks read in full and cross-checked formula-for-formula: **Sheffi
(1985) ch. 6** and **Boyles et al. TNA §6**. Wilson's entropy-maximising gravity model is the
second intellectual parent (via the `(1/β) Σ d(ln d − 1)` term) but has no bibkey in the
canon and is noted, not cited. Canon keys already present: `evans1976derivation`,
`beckmann1956studies`, `florian1974method`, `sheffi1985urban`.

## Decision 1 — Represent the fixed margins as content-hashed scenario data

`CombinedDemand(productions, attractions, beta)` (`core/scenario.py`) carries the fixed
trip-end margins `O_i`, `D_j` and the single shared gravity dispersion `β`. It validates
`Σ O = Σ D` (doubly-constrained feasibility) and `β > 0`, and exposes the reusable
`gravity(od_cost)` — the doubly-constrained Furness / iterative-proportional-fitting
recursion over the interzonal support (`i ≠ j`, `O_i > 0`, `D_j > 0`), made deterministic
(fixed tolerance/iteration cap, exact-row final rescale) so the solver and the harness
recompute byte-identical demand from the same costs.

`Scenario.combined_demand` is optional and **hashed only when set**, appended after the SUE
and elastic fields, so every prior scenario keeps its byte-identical hash — the golden Braess
hash `cf00f411…` is asserted preserved (`test_golden_braess_hash_preserved`). Combined is
mutually exclusive with the SUE fields and `elastic_demand` (each makes the OD demand
non-fixed in an incompatible way). The ordinary `Demand.matrix` carries the **free-flow
gravity** distribution — the deterministic uncongested-equilibrium OD matrix, a meaningful
reference with the right margins and full support.

## Decision 2 — Solve with Evans' partial-linearization Frank-Wolfe

`evans` (`EvansCombinedModel`, paradigm `static_ue_combined`) linearizes only the assignment
(Beckmann) term and keeps the entropy term exact. At iterate `(x, d)` the subproblem

```
min_y  Σ_ij u_ij y_ij + (1/β) Σ_ij y_ij(ln y_ij − 1)   s.t. margins
```

has the closed-form solution `y = gravity(O, D, β, u)` (the doubly-constrained Furness
balancing); its all-or-nothing assignment `w` gives the descent direction, and an **exact
Brent line search** on the combined objective — root of
`g(α) = t(x + α dx)·dx + (1/β) Σ ln(d + α dd)·dd`, nondecreasing on `[0,1]` — sets the step.
`x` is kept a feasible assignment of `d` throughout (`x₀ = AON(gravity at free-flow)`, and
every update advances `x` and `d` by the same step to convex combinations), so the
route-equilibrium gap of `d` stays `≥ 0`. Only **real link flows** are emitted; the auxiliary
gravity `y` is both the FW subproblem solution *and* the demand the harness recomputes.

## Decision 3 — A P1-pure certificate: recompute the demand, then score

The harness knows `O, D, β` (content-hashed), so from the emitted link flows `v` it recomputes
everything (`metrics/gaps.py`, gated on `scenario.combined_demand`), the elastic recipe with
the gravity in place of `D(u)`:

```
t   = link_cost(v)
u   = od_cost_matrix(t)          # per-OD shortest-path cost over the gravity support
d*  = gravity(u)                 # doubly-constrained gravity demand at those costs
relative_gap          = (v·t − Σ u·d*) / (v·t)        # route equilibrium given d*
node_balance_residual = ‖ balance(v) − div(d*) ‖_∞    # demand-consistency + conservation
realized_demand       = Σ d*  (= Σ O_i)               # scored quantity
```

Both are pure functions of `(v, scenario)` — no self-report is trusted (P1) — and the model's
self-reported `relative_gap` is *defined* to equal the scored gap, so the honesty diff is
`~0`. The skim is driven by the gravity **support** (the fixed margins), not the reference
matrix's nonzeros, so a reference entry that underflowed to zero can never desync the solver
from the certificate.

### The feasibility gate — and an honest bound on soundness (adversarial-review finding)

As for elastic (ADR-005), there is no given matrix, so through-node conservation alone is not
a sufficient gate; the gate is `node_balance(v, d*)` (a phantom flow routing zero OD demand
disagrees with `d* > 0` and is censored — regression-tested), plus the negative-excess guard
(`SPTT > TSTT` censored). One property is **specific to combined demand** and must be stated
plainly: the doubly-constrained gravity **always** reproduces the margins `O, D`, so
`node_balance(v, d*)` only certifies that `v` routes the correct *margins* — it carries **no**
information about the OD-pair *distribution* (unlike elastic, where `d* = D(u)` has cost-varying
margins). The only distributional teeth is therefore the negative-excess guard.

**This is NOT a full soundness guarantee, and we do not claim one.** An adversarial review
constructed the exact counterexample: on a *cost-degenerate* instance where every
margin-feasible flow induces the same uniform OD-cost skim `u`, all such flows satisfy
`Σ u·d* = u·T = v·t`, so a wrong-distribution flow (e.g. "dump all trips on the cheapest
links") certifies with `feasible = 1` and `relative_gap = 0` even though it is not the
equilibrium. We verified this is **exactly the aggregate-vs-per-OD limitation the whole harness
already documents** (single-commodity node balance is necessary, not sufficient, for
multi-commodity feasibility): the **fixed-demand** certificate admits the *identical* false
positive on the same network — it is inherited, not introduced by Evans. A fully sound
link-flow-only certificate is impossible here, because distinct margin-feasible distributions
that induce the same skim are indistinguishable at the link level; closing it needs per-OD /
multi-commodity information the "real link flows only" contract withholds (a full
multi-commodity feasibility check is future harness-wide work). We handle it three ways rather
than hide it:

1. **The scored `relative_gap` remains a valid *necessary* condition** — a genuine combined
   equilibrium always passes — and stays P1-pure.
2. **The analytic anchor is deliberately made non-degenerate.** Its near/far link intercepts
   are spaced (1 vs 3) so `c_near(s) − c_far(T − s) = 0.2 s − 3 < 0` for every feasible split;
   the margin-feasible flows form a one-parameter family `v(s) = (s, T−s, T−s, s)` and
   `gap(s) ∝ (s − s*)·(c_near − c_far)` has a **unique** zero at the equilibrium `s* ≈ 6.92`
   (β = 0.5), every other `s` being censored (negative excess) or strictly gapped. So the
   anchor itself does **not** exhibit the limitation, and "dump on the cheapest links" is
   censored on it (regression-tested, `test_anchor_admits_only_the_true_equilibrium`).
3. **The limitation is pinned transparently** by `test_aggregate_multicommodity_limitation`,
   which constructs the degenerate instance, asserts the false positive, and asserts the
   fixed-demand certificate shares it. On any scenario carrying a reference (like the anchor)
   the `flow_rmse_vs_reference` column exposes such flows independently of the gap.

### Convergence and scope

The solver early-stops on `max(route-gap, distribution-gap)`, both non-negative, so
`target_relative_gap` never trips on the transiently-negative combined gap a naive stop would.
The doubly-constrained gravity requires `Σ O = Σ D`; a disconnected instance raises during the
shortest-path step and the certificate censors it. Per-OD dispersion parameters, a
singly-constrained (production-constrained / destination-choice-logit) variant, and
conjugate/bush acceleration of the inner assignment are future extensions.

## Consequences

- **New:** `CombinedDemand`; `Scenario.combined_demand`; paradigm `static_ue_combined`;
  the `evans` model; the combined branch of `Evaluator` (scored `relative_gap`,
  `node_balance_residual`, `realized_demand`); `evans_symmetric_scenario` analytic anchor
  (symmetric bipartite → binary logit split, a scalar fixed point recomputed with brentq —
  flows `(p, q, q, p)`, `p ≈ 6.92` at `β = 0.5`, not trusted; intercepts spaced so the anchor
  is degeneracy-free); `tabench run --scenario evans`.
- **Unchanged:** every prior scenario hash (golden Braess preserved); the fixed-demand / SO /
  SUE / elastic certificate paths; all prior models and tests (201 prior pass, +19 new = 220).
- **Deferred:** per-OD dispersion; singly-constrained / logit destination-choice variant;
  conjugate/bush inner solver; large-network scaling of the `~zones²`-support gravity.