[proofplan] We prove the optimality conditions by formulating the minimum-cost flow problem as a linear program and applying LP duality. The dual variables associated with the flow conservation constraints are the node potentials $\pi_i$. We show that the stated conditions on the reduced costs $\bar{c}_{ij} = c_{ij} - \pi_i + \pi_j$ are exactly the complementary slackness conditions for the primal-dual LP pair, and then invoke the equivalence between complementary slackness and simultaneous primal-dual optimality. [/proofplan] [step:Write the minimum-cost flow problem as a linear program] The minimum-cost flow problem on a directed graph $G = (V, E)$ with $|V| = n$ nodes is: \begin{align*} (\text{Primal}) \qquad \min_{x} \quad & \sum_{(i,j) \in E} c_{ij} x_{ij} \\ \text{subject to} \quad & \sum_{j:(i,j) \in E} x_{ij} - \sum_{j:(j,i) \in E} x_{ji} = b_i \quad \text{for all } i \in V, \\ & \underline{m}_{ij} \leq x_{ij} \leq \overline{m}_{ij} \quad \text{for all } (i,j) \in E, \end{align*} where $b_i$ is the supply (positive) or demand (negative) at node $i$, and $\underline{m}_{ij}$, $\overline{m}_{ij}$ are the lower and upper capacity bounds on edge $(i,j)$. Rewrite the capacity constraints using non-negative slack variables. For each edge $(i,j) \in E$, set $x_{ij} = \underline{m}_{ij} + s_{ij}$ where $0 \leq s_{ij} \leq \overline{m}_{ij} - \underline{m}_{ij}$. Equivalently, introduce upper bound constraints: $s_{ij} + t_{ij} = \overline{m}_{ij} - \underline{m}_{ij}$ with $s_{ij}, t_{ij} \geq 0$. [guided] The minimum-cost flow problem has two types of constraints: flow conservation at each node, and capacity bounds on each edge. To apply LP duality cleanly, we need to identify which constraints produce which dual variables. The flow conservation constraints $\sum_{j:(i,j) \in E} x_{ij} - \sum_{j:(j,i) \in E} x_{ji} = b_i$ are equality constraints, one per node. Their dual variables will be the node potentials $\pi_i$. The capacity constraints $\underline{m}_{ij} \leq x_{ij} \leq \overline{m}_{ij}$ are inequality constraints, two per edge (a lower bound and an upper bound). Their dual variables will give rise to the complementary slackness conditions. [/guided] [/step] [step:Form the dual LP and identify the node potentials] Assign an unrestricted dual variable $\pi_i$ to each flow conservation constraint (one per node $i \in V$), a dual variable $\alpha_{ij} \geq 0$ to each lower capacity constraint $x_{ij} \geq \underline{m}_{ij}$, and a dual variable $\beta_{ij} \geq 0$ to each upper capacity constraint $x_{ij} \leq \overline{m}_{ij}$. The Lagrangian is: \begin{align*} L(x; \pi, \alpha, \beta) = \sum_{(i,j) \in E} c_{ij} x_{ij} &- \sum_{i \in V} \pi_i \Bigl(\sum_{j:(i,j) \in E} x_{ij} - \sum_{j:(j,i) \in E} x_{ji} - b_i\Bigr) \\ &- \sum_{(i,j) \in E} \alpha_{ij}(x_{ij} - \underline{m}_{ij}) + \sum_{(i,j) \in E} \beta_{ij}(x_{ij} - \overline{m}_{ij}). \end{align*} Collecting the coefficient of $x_{ij}$ for each edge $(i,j) \in E$: \begin{align*} \frac{\partial L}{\partial x_{ij}} = c_{ij} - \pi_i + \pi_j - \alpha_{ij} + \beta_{ij}. \end{align*} Setting this to zero (stationarity with respect to the primal variable $x_{ij}$): \begin{align*} c_{ij} - \pi_i + \pi_j = \alpha_{ij} - \beta_{ij}. \end{align*} Define the **reduced cost** $\bar{c}_{ij} := c_{ij} - \pi_i + \pi_j$. The stationarity condition becomes $\bar{c}_{ij} = \alpha_{ij} - \beta_{ij}$ with $\alpha_{ij}, \beta_{ij} \geq 0$. The dual problem is: \begin{align*} (\text{Dual}) \qquad \max_{\pi, \alpha, \beta} \quad & \sum_{i \in V} \pi_i b_i + \sum_{(i,j) \in E} \alpha_{ij} \underline{m}_{ij} - \sum_{(i,j) \in E} \beta_{ij} \overline{m}_{ij} \\ \text{subject to} \quad & \bar{c}_{ij} = \alpha_{ij} - \beta_{ij}, \quad \alpha_{ij} \geq 0, \quad \beta_{ij} \geq 0 \quad \text{for all } (i,j) \in E. \end{align*} [guided] The node potentials $\pi_i$ arise naturally as the dual variables for the flow conservation constraints. The reduced cost $\bar{c}_{ij} = c_{ij} - \pi_i + \pi_j$ measures the "net cost" of sending one unit of flow along edge $(i,j)$ after accounting for the potential difference between nodes $i$ and $j$. This is analogous to the reduced costs in the simplex method. The dual variables $\alpha_{ij}$ and $\beta_{ij}$ are associated with the lower and upper capacity constraints, respectively. The stationarity condition $\bar{c}_{ij} = \alpha_{ij} - \beta_{ij}$ decomposes the reduced cost into two non-negative parts: $\alpha_{ij}$ captures the "shadow price" of the lower bound, and $\beta_{ij}$ captures the "shadow price" of the upper bound. Note that $\alpha_{ij} \geq 0$ and $\beta_{ij} \geq 0$ together with $\bar{c}_{ij} = \alpha_{ij} - \beta_{ij}$ imply: if $\bar{c}_{ij} > 0$ then $\alpha_{ij} > 0$ (and possibly $\beta_{ij} = 0$); if $\bar{c}_{ij} < 0$ then $\beta_{ij} > 0$ (and possibly $\alpha_{ij} = 0$); if $\bar{c}_{ij} = 0$ then either both are zero or both are positive by equal amounts. [/guided] [/step] [step:Derive the complementary slackness conditions] By [Complementary Slackness](/theorems/2559), a primal feasible $x^*$ and dual feasible $(\pi, \alpha, \beta)$ are simultaneously optimal if and only if the complementary slackness conditions hold for every inequality constraint: \begin{align*} \alpha_{ij}(x^*_{ij} - \underline{m}_{ij}) &= 0 \quad \text{for all } (i,j) \in E, \\ \beta_{ij}(\overline{m}_{ij} - x^*_{ij}) &= 0 \quad \text{for all } (i,j) \in E. \end{align*} We now translate these into conditions on the reduced costs. **Case 1: $x^*_{ij} > \underline{m}_{ij}$ (flow strictly above the lower bound).** Then $x^*_{ij} - \underline{m}_{ij} > 0$, so complementary slackness forces $\alpha_{ij} = 0$. From $\bar{c}_{ij} = \alpha_{ij} - \beta_{ij} = -\beta_{ij} \leq 0$. **Case 2: $x^*_{ij} < \overline{m}_{ij}$ (flow strictly below the upper bound).** Then $\overline{m}_{ij} - x^*_{ij} > 0$, so complementary slackness forces $\beta_{ij} = 0$. From $\bar{c}_{ij} = \alpha_{ij} - \beta_{ij} = \alpha_{ij} \geq 0$. **Case 3: $\underline{m}_{ij} < x^*_{ij} < \overline{m}_{ij}$ (flow strictly interior to the capacity interval).** Both Cases 1 and 2 apply simultaneously: $\alpha_{ij} = 0$ and $\beta_{ij} = 0$, so $\bar{c}_{ij} = 0$. [guided] Complementary slackness is the bridge between LP duality and the flow optimality conditions. The principle states that at optimality, whenever an inequality constraint is not tight (i.e., has positive slack), the corresponding dual variable must be zero. For the **lower bound** constraint $x_{ij} \geq \underline{m}_{ij}$: if $x^*_{ij} > \underline{m}_{ij}$ (the constraint is not tight), then $\alpha_{ij} = 0$. Substituting into $\bar{c}_{ij} = \alpha_{ij} - \beta_{ij}$ gives $\bar{c}_{ij} = -\beta_{ij} \leq 0$. In words: if the flow is above its minimum, the reduced cost is non-positive. For the **upper bound** constraint $x_{ij} \leq \overline{m}_{ij}$: if $x^*_{ij} < \overline{m}_{ij}$ (the constraint is not tight), then $\beta_{ij} = 0$. Substituting gives $\bar{c}_{ij} = \alpha_{ij} \geq 0$. In words: if the flow is below its maximum, the reduced cost is non-negative. The contrapositive readings are equally important: - If $\bar{c}_{ij} > 0$, then we must have $x^*_{ij} = \underline{m}_{ij}$ (flow is at its lower bound). - If $\bar{c}_{ij} < 0$, then we must have $x^*_{ij} = \overline{m}_{ij}$ (flow is at its upper bound). - If $0 < \bar{c}_{ij}$, then $\alpha_{ij} > 0$, so $x^*_{ij} = \underline{m}_{ij}$. These are the content of the "reduced cost optimality conditions" stated in the theorem. [/guided] [/step] [step:Prove both directions of the equivalence] **($\Rightarrow$) Optimality implies the conditions.** Suppose $x^*$ is an optimal feasible flow. By [Strong Duality for Linear Programs](/theorems/2553) (the minimum-cost flow LP is feasible by assumption and bounded below since the feasible set is compact when capacities are finite), there exist dual variables $(\pi^*, \alpha^*, \beta^*)$ such that the primal value equals the dual value. By the complementary slackness characterisation of LP optimality, the conditions derived in the previous step hold: $\bar{c}_{ij} \geq 0$ whenever $x^*_{ij} < \overline{m}_{ij}$, and $\bar{c}_{ij} \leq 0$ whenever $x^*_{ij} > \underline{m}_{ij}$. **($\Leftarrow$) The conditions imply optimality.** Suppose $x^*$ is a feasible flow and there exist node potentials $\pi \in \mathbb{R}^n$ such that the stated reduced cost conditions hold. Define $\alpha_{ij}$ and $\beta_{ij}$ by: \begin{align*} \alpha_{ij} &= \max(\bar{c}_{ij}, 0) = \bar{c}_{ij}^{+}, \\ \beta_{ij} &= \max(-\bar{c}_{ij}, 0) = \bar{c}_{ij}^{-}. \end{align*} Then $\alpha_{ij}, \beta_{ij} \geq 0$ and $\bar{c}_{ij} = \alpha_{ij} - \beta_{ij}$, so $(\pi, \alpha, \beta)$ is dual feasible. We verify complementary slackness: - If $x^*_{ij} > \underline{m}_{ij}$, the hypothesis gives $\bar{c}_{ij} \leq 0$, so $\alpha_{ij} = \bar{c}_{ij}^{+} = 0$. Thus $\alpha_{ij}(x^*_{ij} - \underline{m}_{ij}) = 0$. - If $x^*_{ij} < \overline{m}_{ij}$, the hypothesis gives $\bar{c}_{ij} \geq 0$, so $\beta_{ij} = \bar{c}_{ij}^{-} = 0$. Thus $\beta_{ij}(\overline{m}_{ij} - x^*_{ij}) = 0$. Since both primal and dual feasibility hold together with complementary slackness, $x^*$ is primal optimal (and $(\pi, \alpha, \beta)$ is dual optimal). [guided] The forward direction uses the existence of dual optimal variables guaranteed by strong duality. The key hypothesis verification is that the minimum-cost flow LP satisfies the conditions for strong duality: it must be feasible (given by assumption) and bounded (since the flow on each edge is constrained between $\underline{m}_{ij}$ and $\overline{m}_{ij}$, the feasible set is bounded, and a continuous function on a compact set attains its minimum). The converse is constructive: given node potentials $\pi$ satisfying the stated conditions, we explicitly build dual variables $\alpha_{ij}$ and $\beta_{ij}$ that are dual feasible and satisfy complementary slackness with $x^*$. The decomposition $\bar{c}_{ij} = \bar{c}_{ij}^{+} - \bar{c}_{ij}^{-}$ into positive and negative parts is the natural choice. The reduced cost conditions then translate directly into complementary slackness. The fact that complementary slackness plus primal and dual feasibility implies optimality is a standard result from LP duality theory: if $(x^*, \pi^*)$ are primal and dual feasible with zero duality gap (which complementary slackness guarantees), then both are optimal. [/guided] [/step] [step:State the simplified form for uncapacitated networks] In the special case $\underline{m}_{ij} = 0$ for all $(i,j) \in E$ (and $\overline{m}_{ij} = +\infty$ or sufficiently large), the conditions simplify. The upper bound constraint is never active (or vacuous), so $\beta_{ij} = 0$ for all edges, and $\bar{c}_{ij} = \alpha_{ij} \geq 0$ always. Complementary slackness for the lower bound gives: \begin{align*} \bar{c}_{ij} \geq 0 \quad &\text{for all } (i,j) \in E, \\ \bar{c}_{ij} = 0 \quad &\text{whenever } x^*_{ij} > 0. \end{align*} That is, every edge carrying positive flow must have zero reduced cost, and every edge with positive reduced cost must carry zero flow. This completes the proof. [/step]