= Uncapacitated minimum-cost flow
{title2=$\min\{c^Tf:Bf=b,\ f\geq0\}$}
An uncapacitated <minimum-cost flow> has nonnegative edge flows without finite upper capacities. The <flow balances> prescribe net supply at each vertex. For the <oriented incidence matrix> convention with tail $+1$ and head $-1$, vertex <network dual potentials> have <network reduced costs> $c_{ij}-\pi_i+\pi_j$. Nonnegative <network reduced costs> and <complementary slackness> certify a feasible optimum. A feasible negative-cost directed cycle makes the problem unbounded below.
Back to article page
