[proofplan] The reduction proceeds in two stages. First, we eliminate nonzero lower bounds by shifting the flow variables, reducing to a problem with $\underline{m}_{ij} = 0$ for all edges. Second, we construct an equivalent transportation problem by introducing a "supplier" for each edge (representing its capacity) and a "consumer" for each node (absorbing unused capacity and satisfying demand). We verify that the transportation instance faithfully encodes the original flow conservation and capacity constraints, and that the objectives coincide. [/proofplan] [step:Reduce to zero lower bounds by shifting flow variables] For each edge $(i,j) \in E$, define a shifted flow variable: \begin{align*} s_{ij} := x_{ij} - \underline{m}_{ij}. \end{align*} The original capacity constraint $\underline{m}_{ij} \leq x_{ij} \leq \overline{m}_{ij}$ becomes $0 \leq s_{ij} \leq \overline{m}_{ij} - \underline{m}_{ij}$. Define the residual capacity $u_{ij} := \overline{m}_{ij} - \underline{m}_{ij} \geq 0$. Substituting $x_{ij} = s_{ij} + \underline{m}_{ij}$ into the flow conservation constraint at node $i$: \begin{align*} \sum_{j:(i,j) \in E} (s_{ij} + \underline{m}_{ij}) - \sum_{j:(j,i) \in E} (s_{ji} + \underline{m}_{ji}) = b_i. \end{align*} Rearranging: \begin{align*} \sum_{j:(i,j) \in E} s_{ij} - \sum_{j:(j,i) \in E} s_{ji} = b_i - \sum_{j:(i,j) \in E} \underline{m}_{ij} + \sum_{j:(j,i) \in E} \underline{m}_{ji} =: b_i'. \end{align*} The objective transforms as: \begin{align*} \sum_{(i,j) \in E} c_{ij} x_{ij} = \sum_{(i,j) \in E} c_{ij} s_{ij} + \sum_{(i,j) \in E} c_{ij} \underline{m}_{ij}. \end{align*} The second sum is a constant independent of the decision variables. Therefore minimising $\sum c_{ij} x_{ij}$ over the original problem is equivalent to minimising $\sum c_{ij} s_{ij}$ over the shifted problem with supplies $b_i'$, zero lower bounds, and upper bounds $u_{ij}$. [guided] The shift $x_{ij} \mapsto s_{ij} = x_{ij} - \underline{m}_{ij}$ is a standard technique for eliminating nonzero lower bounds. The idea is that we "pre-ship" $\underline{m}_{ij}$ units along each edge and then optimise over the remaining capacity. Why do the supplies change? The pre-shipped flow $\underline{m}_{ij}$ along edge $(i,j)$ removes $\underline{m}_{ij}$ units from node $i$'s outflow budget and adds $\underline{m}_{ij}$ to node $j$'s inflow. This shifts the net supply at node $i$ by $-\underline{m}_{ij}$ for each outgoing edge and $+\underline{m}_{ji}$ for each incoming edge, yielding the adjusted supply: \begin{align*} b_i' = b_i - \sum_{j:(i,j) \in E} \underline{m}_{ij} + \sum_{j:(j,i) \in E} \underline{m}_{ji}. \end{align*} The total supply is preserved: $\sum_i b_i' = \sum_i b_i$ (each lower bound $\underline{m}_{ij}$ appears once with a negative sign at node $i$ and once with a positive sign at node $j$, cancelling in the sum). [/guided] [/step] [step:Handle infinite capacities when costs are non-negative] After the shift, all lower bounds are zero and upper bounds are $u_{ij} = \overline{m}_{ij} - \underline{m}_{ij}$. If some $u_{ij} = +\infty$ (i.e., the original edge had $\overline{m}_{ij} = +\infty$), we need finite capacities for the transportation formulation. When $c_{ij} \geq 0$ (as guaranteed by the theorem's hypothesis in the infinite-capacity case), the optimal flow along any edge is bounded by the total supply in the network. Define \begin{align*} M := \sum_{i \in V: b_i' > 0} b_i'. \end{align*} This is the total positive supply in the shifted problem. No optimal flow can send more than $M$ units along any single edge, because the total flow entering the network from supply nodes is exactly $M$. Therefore, replacing $u_{ij} = +\infty$ with $u_{ij} = M$ does not change the optimal solution. After this replacement, all capacities are finite. [guided] Why does capping at $M$ preserve optimality? The total flow entering the network from all supply nodes is $M = \sum_{i: b_i' > 0} b_i'$. On any edge $(i,j)$, the flow $s_{ij}$ cannot exceed $M$ because flow is conserved: no more than $M$ units of flow exist in the entire network. Since $c_{ij} \geq 0$, sending flow along edge $(i,j)$ has non-negative cost, so an optimal solution would never route more flow than necessary. Thus $s_{ij} \leq M$ at any optimum, and imposing $u_{ij} = M$ is not binding. This step fails if some $c_{ij} < 0$ with $u_{ij} = +\infty$, because the optimal solution might send arbitrarily large flow along a negative-cost edge (creating an unbounded problem). The theorem's hypothesis — finite capacities or non-negative costs — rules out this pathology. [/guided] [/step] [step:Construct the transportation instance] We now have a minimum-cost flow problem with zero lower bounds and finite upper bounds $u_{ij}$ on all edges, supply values $b_i'$ at each node, and edge costs $c_{ij}$. We construct an equivalent transportation problem. **Suppliers:** For each edge $(i,j) \in E$, create a supplier $S_{ij}$ with supply equal to $u_{ij}$ (the capacity of edge $(i,j)$). **Consumers:** For each node $i \in V$, create a consumer $D_i$ with demand: \begin{align*} d_i := \sum_{k:(i,k) \in E} u_{ik} - b_i'. \end{align*} **Transportation links and costs:** Supplier $S_{ij}$ is connected to exactly two consumers: - To consumer $D_j$ (the head of edge $(i,j)$) with transportation cost $c_{ij}$. - To consumer $D_i$ (the tail of edge $(i,j)$) with transportation cost $0$. Let $f_{ij \to j}$ denote the amount shipped from supplier $S_{ij}$ to consumer $D_j$, and $f_{ij \to i}$ the amount shipped from $S_{ij}$ to consumer $D_i$. [guided] The construction encodes the flow problem as a bipartite matching between "edge capacities" (suppliers) and "node demands" (consumers). The intuition is as follows: Each edge $(i,j)$ has $u_{ij}$ units of capacity. Of these, $s_{ij}$ units carry flow from $i$ to $j$ (incurring cost $c_{ij}$ per unit), and the remaining $u_{ij} - s_{ij}$ units are "unused capacity" that stays at node $i$ (at zero cost). In the transportation model: - Supplier $S_{ij}$ represents the $u_{ij}$ available units on edge $(i,j)$. - Shipping $f_{ij \to j} = s_{ij}$ units to consumer $D_j$ at cost $c_{ij}$ represents sending flow along the edge. - Shipping $f_{ij \to i} = u_{ij} - s_{ij}$ units to consumer $D_i$ at cost $0$ represents unused capacity. The demand $d_i = \sum_{k:(i,k) \in E} u_{ik} - b_i'$ at consumer $D_i$ accounts for the unused capacity arriving at node $i$ from all outgoing edges, adjusted by the net supply. This is designed so that the transportation balance constraints reproduce the original flow conservation constraints. [/guided] [/step] [step:Verify the supply-demand balance in the transportation instance] The total supply in the transportation problem is $\sum_{(i,j) \in E} u_{ij}$. The total demand is: \begin{align*} \sum_{i \in V} d_i &= \sum_{i \in V} \Bigl(\sum_{k:(i,k) \in E} u_{ik} - b_i'\Bigr) = \sum_{(i,j) \in E} u_{ij} - \sum_{i \in V} b_i'. \end{align*} Since $\sum_{i \in V} b_i' = \sum_{i \in V} b_i = 0$ (flow conservation requires the total supply to equal the total demand in the original network), we have: \begin{align*} \sum_{i \in V} d_i = \sum_{(i,j) \in E} u_{ij} = \text{total supply}. \end{align*} The transportation problem is balanced, as required. [/step] [step:Verify that the transportation constraints recover the original flow conservation] The supply constraint for supplier $S_{ij}$ is: \begin{align*} f_{ij \to j} + f_{ij \to i} = u_{ij}. \end{align*} Setting $s_{ij} := f_{ij \to j}$, this gives $f_{ij \to i} = u_{ij} - s_{ij}$. The capacity constraint $0 \leq s_{ij} \leq u_{ij}$ follows from $f_{ij \to j} \geq 0$ and $f_{ij \to i} \geq 0$. The demand constraint for consumer $D_i$ is: \begin{align*} \sum_{j:(j,i) \in E} f_{ji \to i} + \sum_{k:(i,k) \in E} f_{ik \to i} = d_i. \end{align*} Substituting $f_{ji \to i} = s_{ji}$ (flow arriving at $i$ along edge $(j,i)$) and $f_{ik \to i} = u_{ik} - s_{ik}$ (unused capacity on edge $(i,k)$): \begin{align*} \sum_{j:(j,i) \in E} s_{ji} + \sum_{k:(i,k) \in E} (u_{ik} - s_{ik}) = \sum_{k:(i,k) \in E} u_{ik} - b_i'. \end{align*} Rearranging: \begin{align*} \sum_{j:(j,i) \in E} s_{ji} - \sum_{k:(i,k) \in E} s_{ik} = -b_i', \end{align*} which is equivalent to: \begin{align*} \sum_{k:(i,k) \in E} s_{ik} - \sum_{j:(j,i) \in E} s_{ji} = b_i'. \end{align*} This is exactly the flow conservation constraint at node $i$ in the shifted problem. [guided] This is the verification that the transportation model faithfully encodes the original flow problem. Each consumer $D_i$ receives flow from two types of sources: 1. **Flow along incoming edges**: for each edge $(j,i) \in E$, supplier $S_{ji}$ ships $f_{ji \to i} = s_{ji}$ units at cost $c_{ji}$ to consumer $D_i$. This represents actual network flow arriving at node $i$. 2. **Unused capacity on outgoing edges**: for each edge $(i,k) \in E$, supplier $S_{ik}$ ships $f_{ik \to i} = u_{ik} - s_{ik}$ units at zero cost to consumer $D_i$. This represents capacity on edge $(i,k)$ that is not used. The demand equation at $D_i$ sums these two contributions and sets them equal to $d_i = \sum_k u_{ik} - b_i'$. After algebraic simplification, the unused-capacity terms $\sum_k u_{ik}$ cancel between the two sides, leaving exactly the flow conservation equation $\sum_k s_{ik} - \sum_j s_{ji} = b_i'$. [/guided] [/step] [step:Verify the objectives coincide and conclude the equivalence] The transportation objective is: \begin{align*} \sum_{(i,j) \in E} c_{ij} \cdot f_{ij \to j} + \sum_{(i,j) \in E} 0 \cdot f_{ij \to i} = \sum_{(i,j) \in E} c_{ij} \, s_{ij}. \end{align*} This equals the shifted flow objective $\sum_{(i,j) \in E} c_{ij} s_{ij}$, which differs from the original objective by the constant $\sum_{(i,j) \in E} c_{ij} \underline{m}_{ij}$. We have established a bijection between feasible flows $s$ in the shifted minimum-cost flow problem and feasible transportation plans $(f_{ij \to j}, f_{ij \to i})_{(i,j) \in E}$, given by $s_{ij} = f_{ij \to j}$ and $u_{ij} - s_{ij} = f_{ij \to i}$. The objectives coincide under this bijection. Therefore the two problems have the same optimal solutions (up to the bijection) and the same optimal value (up to the additive constant). This completes the reduction. [/step]