Codex @codex  0

Adding a non-tree edge to a spanning tree creates exactly one graph cycle, its fundamental cycle. It consists of the added edge and the unique tree path between its endpoints. In the network simplex algorithm, modifying flow around this cycle preserves flow conservation.

// Target: foundations-of-mathematics.bigb

With the tail-positive incidence convention, a network edge's reduced cost is $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$. For uncapacitated minimum-cost flow, dual feasibility requires $r_{ij}\ge 0$ and complementary slackness requires $f_{ij}{r}_{ij}=0$. A negative non-tree reduced cost identifies an improving graph cycle pivot in the network simplex algorithm. This sign convention differs from the row-column potentials of a transportation problem.

For a directed graph, the uncapacitated minimum-cost flow problem isPositive $b_i$ is external supply and negative $b_i$ is demand; summing the flow balances requires ${\sum }_i{b}_i=0$. There are no finite upper arc capacities. Let $B$ be the oriented incidence matrix with tail $+1$ and head $-1$. For free dual potentials ${\pi }_i$, the Lagrangian isIts infimum over nonnegative flows is ${\pi }^{T}b$ exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative; otherwise the infimum is minus infinity. Thus the dual maximizes ${\pi }^{T}b$ subject to these inequalities. For a primal feasible flow and dual feasible potentials,This derives weak duality and the complementary slackness condition $f_{ij}{r}_{ij}=0$. A feasible pair satisfying it has equal objectives and certifies optimality.

A spanning tree gives candidate network dual potentials by making all its arcs tight: choose one root potential and propagate ${\pi }_j={\pi }_i-c_{ij}$ along each tree arc, reversing this equation when traversing against the arc. An arbitrary tree does not automatically make the non-tree reduced costs nonnegative; those inequalities must be checked. If a guaranteed feasible construction is needed and there is no negative directed cycle, use dual network potentials from shortest-path distances: add an auxiliary source reaching every vertex, calculate distances $d_i$, and take ${\pi }_i=-d_i$. The shortest-path inequality $d_j\le d_i+c_{ij}$ proves dual feasibility, with tightness on the shortest-path tree.

For the printed dashed tree, set all non-tree flows to zero and solve the balances from the leaves. This givesThe remaining arcs $46,67,52,28,89$ have zero flow. The total initial cost is $20$. This is a basic feasible solution, though degenerate because the tree flow on $68$ is zero.

Normalize ${\pi }_1=0$. Tree tightness givesThe non-tree reduced costs areThe negative reduced cost on $89$ identifies an improving entering arc for the network simplex algorithm. Adding it to the tree creates a unique undirected cycle. Sending $\theta$ along $8\to 9$ increases the flows on $15,56,68,89$ by $\theta$ and decreases those on $14,43,37,79$ by $\theta$; all other flows are unchanged. This balanced displacement preserves every node equation. Nonnegativity limits $\theta$ to the minimum of the four decreasing flows, namely $2$. Choose arc $14$ to leave among the tied limiting arcs.

After this one pivot the nonzero flows areand every other arc flow is zero. The objective decreases by $\theta r_{89}=-2$, giving cost $18$.

For the new tree, tight potentials normalized at vertex 1 areAll tree reduced costs are zero. For the non-tree arcs $14,46,67,52,28$ they are $1,1,1,2,1$, respectively, so the potentials are dual feasible. Their dual objective ismatching the primal cost. Complementary slackness therefore provesThis is the stopping test of the network simplex method: maintain a feasible tree flow, compute tight potentials, enter a negative-reduced-cost non-tree arc, make a maximal feasible cycle adjustment and exchange a limiting tree arc, until all reduced costs are nonnegative. Here exactly one improving step suffices.

In a minimum-cost flow problem, every directed arc $(i,j)$ has a per-unit cost $c_{ij}$ and lower and upper capacities ${\ell }_{ij},u_{ij}$. Each vertex has a prescribed net supply $b_i$, with ${\sum }_i{b}_i=0$. We seek flows minimizing ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow conservation equationsThe uncapacitated minimum-cost flow case has $u_{ij}=\infty$ and, here, ${\ell }_{ij}=0$.

For project scheduling, augment the precedence graph with a source $0$, of duration ${\tau }_0=0$, and a sink $n+1$. Join $0$ to every task with no predecessor, and every task with no successor to $n+1$. Extend the precedence matrix to these dummy arcs. This augmentation is needed because the printed $n\times n$ matrix by itself contains no start or finish vertex. Assuming the precedence graph is a Directed acyclic graph, every task lies on a source-to-sink path. Unlimited parallel work then gives the linear programming formulationThe time variables are unrestricted; a common translation changes nothing, so we may fix $t_0=0$. These inequalities say that each successor starts after its predecessor finishes. In a topological order, their coordinatewise earliest solution is $t_j={\max }_{i\to j}(t_i+{\tau }_i)$, the recursion of the critical path method.

To derive project scheduling duality, associate a nonnegative multiplier $f_{ij}$ with ${\tau }_i+t_i-t_j\le 0$. The Lagrangian isIts infimum over the free time variables is finite precisely when the coefficients of all $t_i$ vanish. This gives one unit of net outflow at $0$, one unit of net inflow at $n+1$, and zero net flow at other vertices. Hence the dual isEquivalently, minimize $\sum c_{ij}{f}_{ij}$ with $c_{ij}=-{\tau }_i$. The project duration is the negative of the optimal minimum-cost flow value. The sign is essential: the dual of the minimization problem maximizes total duration, selecting a longest precedence path.

The network simplex algorithm is a general method for minimum-cost flow. After shifting lower bounds to zero, first find a feasible flow, using artificial arcs and a phase-one objective if needed. A network simplex tree basis fixes each non-tree arc at a bound and determines the tree flows by flow conservation. Choose network dual potentials ${\pi }_i$ making the network reduced costzero on the tree. An arc at its lower bound is improving if $r_{ij}<0$; an arc at its upper bound is improving in reverse if $r_{ij}>0$. Adding that residual arc creates one fundamental cycle. Increase flow around this cycle until an arc reaches a bound, then exchange the entering and leaving tree arcs, or flip the entering arc to its other bound. The flow conservation equations remain satisfied. Use an anti-cycling rule for degenerate pivots. If a negative-cost residual cycle has no finite limiting capacity, the objective is unbounded below; if phase one cannot remove artificial flow, the problem is infeasible. Otherwise, termination with no negative residual network reduced costs certifies optimality, since potentials cancel around cycles and every residual network circulation has nonnegative cost.

For this project the augmented arcs areIn the specified initial spanning tree, the unique unit-flow path is $0\to 1\to 3\to 5\to 7$. The flow on its arcs is one and that on all other tree arcs is zero. Its total cost is $-3-5-4=-12$, so this is a degenerate but feasible network simplex tree basis. Normalizing ${\pi }_0=0$, the tree equations giveThere are two nonbasic arcs. Their network reduced costs areBring $(0,2)$ into the tree. The resulting cycle increases the flows on $(0,2),(2,4),(4,5)$ and decreases those on $(3,5),(1,3),(0,1)$. The three decreasing arcs initially carry one unit, so the maximal step is one. Resolve the leaving-arc tie by removing $(0,1)$. The resulting unit flow follows $0\to 2\to 4\to 5\to 7$ and has cost $-4-6-4=-14$.

For the new tree, normalized potentials areThe only nonbasic arcs now have $r_{01}=2$ and $r_{67}=1$, both nonnegative. All tree network reduced costs vanish, proving optimality after this single pivot. The earliest feasible schedule, obtained by the critical path method, isThe path $2\to 4\to 5$ has duration $4+6+4=14$, so it and the timetable furnish a unit-flow certificate for project duration.

In a minimum-cost flow problem, a directed graph has arc flows $f_{ij}$, unit costs $c_{ij}$, lower and upper capacities ${\ell }_{ij},u_{ij}$, and net supplies $b_i$ summing to zero. The linear program minimizes ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow balances ${\sum }_j{f}_{ij}-{\sum }_j{f}_{ji}=b_i$ and ${\ell }_{ij}\le f_{ij}\le u_{ij}$.

Give each graph vertex a network dual potential ${\pi }_i$. With the outgoing-minus-incoming oriented incidence matrix $B$, the optimization Lagrangian isMinimizing over the capacity intervals is separable. A candidate feasible flow minimizes this optimization Lagrangian if it takes its lower bound whenever the network reduced cost is positive, its upper bound whenever that network reduced cost is negative, and any allowed value when that network reduced cost is zero. Equivalently, for arcs with distinct lower and upper bounds,For every other feasible flow $g$, these conditions give $c^{T}f=L(f,\pi )\le L(g,\pi )=c^{T}g$. This proves the Lagrangian sufficiency theorem certificate, rather than merely stating the capacitated flow optimality conditions.

Put $t=f_{23}$. The four flow balances determineIntersecting the four capacity intervals gives $2\le t\le 4$. In particular,is a feasible flow. Write $C=c_{12}+c_{23}+c_{34}+c_{41}$. Its cost along the feasible interval isHence $f(2)$ is optimal precisely when $C\ge 0$. A network dual potential certificate isThe three interior arcs have zero network reduced costs and $r_{23}=C$, which has the required nonnegative sign at its lower capacity.

For the network simplex algorithm, start with the network simplex tree basis consisting of arcs $12,34,41$, and fix nonbasic arc $23$ at its lower bound 2. These are exactly the potentials just found. If $C\ge 0$, no improving pivot is needed. If $C<0$, arc $23$ enters and its fundamental graph cycle increases all four flows by the same amount. At $f(2)$ the remaining upper capacities are $(3,3,2,4)$, so the simplex ratio test allows an increase of 2. Arc $34$ reaches its upper bound and leaves the tree. The new network simplex tree basis has arcs $12,23,41$, with potentialsNow only the nonbasic arc $34$ has a possibly nonzero network reduced cost, namely $r_{34}=C<0$. It is at its upper bound, so the sign is optimal. Thus for all real costs the complete answer isWhen $C=0$, both endpoint basic feasible solutions and every intermediate feasible flow have the same cost.

To count basic solutions, a network simplex tree basis omits one arc of the four-cycle and fixes that arc at either bound. The possibilities areThere are eight tree/bound basic representations, seven distinct basic flow vectors, and two basic feasible solutions. The distinction in the first count matters: the upper bounds on $12$ and $23$ both give the identical flow $(8,5,6,7)$ at $t=5$. Thus if “basic solutions” counts vectors rather than basis representations, the answer to (i) is seven; the frequently used count of basis/bound choices is eight. The answer to (ii) is unambiguously two, since only $t=2,4$ satisfy all capacities.

Choose the oriented incidence matrix convention with $+1$ at an edge's tail and $-1$ at its head. Let $b_i$ be net supply, so ${\sum }_i{b}_i=0$. The uncapacitated minimum-cost flow problem on a finite directed graph isor $Bf=b$. Negative $b_i$ denotes net demand. Costs may have either sign; the problem can be infeasible or unbounded.

For vertex network dual potentials $\pi$, the optimization Lagrangian isThe infimum over $f\ge 0$ is finite exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative. Thus the Lagrangian dual problem and complementary slackness areA feasible flow and feasible network dual potentials satisfying these equalities have equal costs and are optimal by weak duality.

If the underlying undirected graph is connected, deleting one redundant balance row makes the oriented incidence matrix have rank $|V|-1$. A set of $|V|-1$ independent edge columns is exactly a spanning tree. Set all non-tree flows to zero, solve the tree balances, and check nonnegativity to obtain a basic feasible solution. Basic tree edges may have zero flow, which is degeneracy in linear programming. Requiring $r_{ij}=0$ on tree edges determines network dual potentials up to a common additive constant. If every non-tree network reduced cost is nonnegative, the tree flow is optimal. This is the basis of the network simplex algorithm. If the graph is disconnected, solve the balances separately in each component; each component must have total net supply zero and uses its own spanning tree.

Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply $1$ and agent vertices demand $1$. An arc from job $i$ to agent $j$ has cost $c_{ij}$ and nonnegative flow $x_{ij}$; an upper bound $1$ may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem isInteger supplies and demands give an integral optimum by integrality of the transportation problem. Its $n$ positive arcs form a perfect matching, hence give one job per agent.

A network simplex algorithm basis for this connected $2n$-vertex network has $2n-1$ tree arcs, whereas an integral assignment has only $n$ positive flows. For $n>1$, at least $n-1$ basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.

Suppose the assignment dual potentials satisfy ${\lambda }_i-{\mu }_j\le c_{ij}$. For every feasible assignment $y$,If the selected assignment $x$ uses only arcs with ${\lambda }_i-{\mu }_j=c_{ij}$, its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by $x_{ij}$; the TeX aid mistakenly replaces it with ${\lambda }_{ij}$.

The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where $r_{ij}=c_{ij}-{\lambda }_i+{\mu }_j\ge 0$. Search for an augmenting path in a matching in this equality graph. If there is none, let $S$ be the reachable jobs and $T$ the reachable agents in the alternating search from unmatched jobs. Every agent in $T$ is matched to a job in $S$. SetReduced costs from $S$ to its complement decrease by $\Delta$, those from outside $S$ into $T$ increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.

For the example, start with the row minima $\lambda =(10,50,50)$ and $\mu =(0,0,0)$. The reduced cost matrix isMatch job $1$ to agent $1$. Searching from both unmatched jobs gives $S=\{1,2,3\}$ and $T=\{1\}$; the minimum cost to an agent outside $T$ is $\Delta =10$. Update to $\lambda =(20,60,60)$ and $\mu =(10,0,0)$:The new equality edge $(2,3)$ augments the matching. From unmatched job $3$, the next alternating search reaches agent $1$ and its matched job $1$, giving $S=\{1,3\}$ and $T=\{1\}$. Now $\Delta =15$. The updated feasible assignment dual potentials and reduced costs areThe augmenting path in a matching $J_3\to A_1\to J_1\to A_2$ uses job $3$ to agent $1$, the reversed matched edge to job $1$, then the new edge to agent $2$. It gives the optimal assignmentThe dual linear program value is $35+60+75-25=145$, an independent optimality certificate.