Auditing a Time-Expanded Multi-Commodity Flow MIP

Audit a time-expanded multi-commodity flow MIP formulation for correctness: verify variable index domains against the horizon and transit times, check flow conservation with the proper transit-time shift on inflow, validate that bundle (capacity) constraints are summed correctly across commodities at each time step, and confirm that sink demand-satisfaction constraints respect the departure-time index domain.

Step 1 of 157%

Tutorial

Variables and Index Domains

A time-expanded multi-commodity flow (MCF) MIP routes commodities $k\in K$ through a network $(N,A)$ over a discrete horizon $\{0,1,\dots,T\}$ . The core decision variable is

x^k_{ij,t} \;=\; \text{flow of commodity } k \text{ entering arc } (i,j) \text{ at time } t.

Each arc $(i,j)$ has transit time $\tau_{ij}\ge 1$ : flow that enters at time $t$ arrives at $j$ at time $t+\tau_{ij}$ .

When auditing the variable declarations, check that the index ranges respect the horizon. Since arrival cannot exceed $T$ , the departure index must satisfy

0 \;\le\; t \;\le\; T - \tau_{ij}.

A formulation that declares $x^k_{ij,t}$ for all $t\in\{0,\dots,T\}$ silently allows flow to arrive past the horizon — a common formulation bug. For example, with $T=6$ and $\tau_{ij}=2$ , the correct departure domain is $t\in\{0,1,2,3,4\}$ ; the values $t=5$ and $t=6$ would route flow to arrive at times $7$ and $8$ , after the horizon ends.