Augmenting path in a matching Created 2026-10-06 Updated 2026-10-14
An augmenting path in a matching is a nonempty alternating path in a matching with distinct endpoints that are both unmatched vertices in a matching. Its first and last edges lie outside . Thus it has unselected edges and selected edges, for some . Taking the symmetric difference
removes the selected edges on and inserts its unselected edges. Each internal vertex exchanges one selected edge for another; each endpoint gains its first selected edge. All choices away from stay in place, so is a matching in a graph with .[ref]
For an explicit repair, let the path graph have vertices in that order and start with
The endpoints and are initially unmatched vertices in a matching. Along the edges are outside, inside, outside, inside, outside . Remove and , then add together:
This raises the cardinality from two to three and gives a perfect matching. Six vertices allow at most three disjoint pairs, so it is also a maximum cardinality matching. The initial is already a maximal matching: every unused edge touches a matched vertex. Augmentation succeeds because it can replace earlier choices instead of only adding to them.
Figure 1.
The augmenting path in a matching on P₆ replaces two selected edges by three using symmetric difference
. Details.
One unused edge joining two unmatched vertices in a matching is the shortest possible augmenting path in a matching. Longer augmenting paths in a matching reassign several partners, explaining why a stalled greedy matching need not be optimal. For edge benefits , the change in total benefit is
which need not be positive even though the cardinality increases. A maximum-weight matching therefore needs a different optimality test. In an assignment equality graph an augmenting path in a matching moves toward a perfect matching while preserving zero reduced costs on matched edges; this is the setting used by the Hungarian algorithm.
Dantzig pivot rule 2026-10-14
In maximization, select the entering nonbasic variable with greatest positive reduced cost, meaning objective increase per unit of that variable. Unlike geometric steepest-edge pricing, this rate depends on variable and constraint scaling. A rescaled Klee-Minty cube can give the same -pivot path as smallest-index improving-facet pivoting.
Dual feasibility 2026-10-14
For minimization with constraints , , a dual-feasible vector obeys , so is a lower bound on every primal-feasible objective value. For a simplex dictionary with basis matrix , the associated vector is . Its basic reduced costs are zero and its nonbasic reduced costs are . Thus nonnegative reduced costs are exactly dual feasibility in this minimization convention; basic primal values may still be negative, as in the dual simplex algorithm.
For a feasible simplex dictionary, let be a nonbasic variable's improving reduced cost and let be its largest feasible increase from the simplex ratio test. The greatest improvement pivot rule chooses an entering variable maximizing . It measures the improvement over the entire edge, whereas the Dantzig pivot rule maximizes only .
Hungarian algorithm Created 2026-10-06 Updated 2026-10-14
The Hungarian algorithm maintains feasible assignment dual potentials and a matching of equality edges. If the alternating search cannot augment, adjust reachable job and agent potentials by the smallest reduced cost leaving the search set. This preserves feasibility and existing matching equalities while exposing a new equality edge. A resulting perfect matching attains the dual lower bound.
Linear programming sensitivity within a fixed optimal basis Created 2026-10-06 Updated 2026-10-14
For a linear program with unchanged cost and constraint matrix, an optimal simplex basis remains optimal while its basic solution remains feasible. Its reduced costs and dual certificate do not change. The new basic variables are , and the objective is the displayed affine function, with the basis's dual solution. This gives an exact piecewise-affine sensitivity region, determined by nonnegativity of the basic variables, rather than merely a formal first derivative.
Network simplex algorithm Created 2026-10-06 Updated 2026-10-14
The network simplex algorithm specializes the simplex algorithm to network flows. A basis is represented by a spanning tree with nonbasic flows at their bounds; potentials give reduced costs, and entering arcs produce cycle pivots. Degeneracy in linear programming is particularly common in assignment instances.
Use the original PDF constraints, whose right sides are and . Introduce nonnegative surplus variables , slack , and artificial variables :
All seven variables are nonnegative. Phase I of the two-phase simplex method minimizes with initial basis . The initial simplex dictionary is
Enter and leave : the ratio test gives . Substituting gives
Now enter and leave . The bounds from are , so the ratio test selects . The new dictionary is
The associated basic solution has and , which is a global minimum because artificial variables are nonnegative. Delete their columns for Phase II. In the remaining basis the objective is
For , both reduced costs are nonnegative, so the simplex method has reached the optimum at :
For , the coefficient of is negative. Enter ; the ratio test gives from and from , so leaves. Eliminating gives
and hence
The two reduced costs are now positive, so is optimal and
At the whole feasible edge from to is optimal; both value formulas agree. These dictionaries explicitly carry out both phases rather than inferring the answer solely from a feasible-region sketch.
Introduce nonnegative slack variables , a nonnegative surplus variable , and an artificial variable . Phase I of the two-phase simplex method minimizes . The initial simplex dictionary is
With the nonbasic variables zero this is feasible for the artificial problem. Enter ; the minimum ratios are , so leaves. Solving its row for and substituting gives
Now enter . The ratios from decreasing basic variables are and , so leaves. The resulting dictionary is
Setting the nonbasic variables zero gives , so Phase I has reached its minimum and found feasibility. Remove and reinstate the true objective . Substitution of the basic variables gives
Enter . The decreasing rows give ratios for and for , so leaves. Phase II then has
Every nonbasic variable is nonnegative and every reduced cost is positive. Thus the simplex optimality criterion proves
All three original constraints are active. Positivity of all three reduced costs also proves uniqueness: equality in the objective lower bound forces , which fixes the displayed solution.
For the linear program in maximization form, a nonnegative multiplier of the resource inequalities gives
whenever . Equivalently, the Lagrangian is ; its supremum over is finite exactly when . Minimizing this bound gives the dual linear program
The displayed inequality proves weak duality directly.
For the final simplex tableau, the basic-variable order is . With interpreted as the ordinary unpriced slack variables, its constraint equations give
The bottom row is read in the reduced-cost convention , with right side minus the basic objective value. It says the reduced costs of are . Thus optimality requires , while can increase without changing the objective until reaches zero. The complete primal optimum set is
Reconstructing a linear program from a final simplex tableau exposes a source inconsistency. The slack columns are
Because the first basic column is that of , the original constraint data are
The slack reduced costs give and
Consequently the recovered homogeneous linear program is
Every point in the optimum segment has value . Since the segment contains a point with both variables positive, complementary slackness forces both dual column inequalities to be equalities. They give the unique dual optimum
The printed bottom-right entry is , but it must be for this linear objective and these constraint rows. Thus no original problem in the stated homogeneous standard form has exactly the entire printed tableau. Changing that one entry to gives the reconstructed problem above. Alternatively, if an affine objective is permitted, has the displayed optimum value and unchanged reduced costs; the corresponding affine dual objective is . Both interpretations have exactly the same primal and dual optimizer sets. The discrepancy is in the objective constant, not in the optimal segment.
Introduce nonnegative slack variables and write for the objective value. The initial simplex dictionary, recovered from the original PDF rather than the corrupted converted table, is
For this minimization convention, nonnegative objective coefficients give dual feasibility. The dual simplex algorithm repairs a negative basic value while retaining those nonnegative reduced costs. If the leaving row is , , an entering variable must have ; choose the smallest ratio of its objective coefficient to .
Choose to leave. Eligible columns are , with ratios and . Thus enters. Solving its row and substituting gives
Now only has a negative basic value. Its only eligible entering column is , so pivot there, with leaving. The resulting dictionary is
Setting the nonbasic variables to zero gives a basic feasible solution. The final objective row also proves for every feasible point, because its nonbasic variables are nonnegative. Hence the unique relaxed optimum is
For the integer program, all four original slack variables are integers whenever the decision variables are integers. The fractional row can be written
The Gomory fractional cut keeps the fractional parts of these coefficients: and . It therefore gives , or . Its validity can also be seen directly: the displayed row makes an odd nonnegative integer. In original variables this cut is .
Introduce the new integer-valued slack , with initial row . It is primal infeasible but retains dual feasibility, so one more dual-simplex pivot has leave and enter. Substitute to obtain
All basic values at are nonnegative integers, including . The objective row proves a lower bound of on every point satisfying the valid cut, hence on every integer-feasible point. It is attained at
The strictly positive nonbasic objective coefficients also show uniqueness. One Gomory cut and its reoptimization are sufficient.
Introduce slack variables . The initial simplex dictionary is
All six variables are nonnegative. The given rule is the Dantzig pivot rule: select the nonbasic variable with the largest positive reduced cost. It applies to slack variables too once they become nonbasic. At each step the simplex ratio test limits how far that entering variable can increase before a basic variable reaches zero.
The successive objective rows of the simplex dictionary, expressed in the current nonbasic variables, are
These rows identify each entering variable unambiguously. Performing the corresponding simplex ratio tests gives the complete pivot sequence:
For example, after pivot two the dictionary has , and . Although increasing improves the objective at rate four, reaches zero first at , giving pivot three. After pivot four, and ; the upper bound gives pivot five.
In the final objective row every reduced cost is nonpositive. Since , it also directly certifies the upper bound , attained only when all three vanish. Thus
A greatest improvement pivot rule uses the total feasible increase in the objective, rather than its increase per unit of the entering variable. At the origin, the three candidate edge moves have improvements , and . It therefore brings into the simplex basis first, with leaving, and immediately reaches the optimum. This rule solves this instance in one pivot.
This is a three-dimensional Klee-Minty cube example: the specified Dantzig pivot rule visits every vertex before reaching the optimum. Higher-dimensional versions require pivots, so that rule has exponential worst-case running time despite its strong practical performance. Each pivot requires only polynomially many arithmetic operations. An anti-cycling rule such as the Bland pivoting rule ensures finite termination; without one, degenerate pivots can cycle. A crude terminating bound is the number of possible bases, for constraints and original variables, which can be exponential. This does not show that every conceivable pivot rule must take exponential time. Linear programming itself has polynomial-time algorithms, including the ellipsoid method and suitable interior-point methods.
Encode a vertex of a polytope by three bits: bit records whether the lower or upper bound of coordinate is tight. Every choice is possible because , and the triangular active equations determine that vertex of a polytope uniquely. Its three adjacent vertices of a polytope are obtained by changing one bit. The geometric Bland pivoting rule specified here chooses the smallest-index active facet that can be left while increasing . It produces the following path; the final column records the facet left on arrival at the next vertex of a polytope:
For example, at the origin all three outgoing edges improve the objective, but leaving facet 1 has priority. At bit string , switching bit 2 decreases , so the rule switches bit 1, leaving facet 2. At , neither of the earlier-coordinate switches improves , so the rule finally leaves facet 5. The upper face reverses the direction in which changes of improve , and the remaining three horizontal pivots follow. The objective values in the table are strictly increasing for the stated range of .
Figure 1.
Seven Bland pivots through all eight vertices of the Klee-Minty cube, with epsilon equal to one quarter
. Details.
Thus the simplex method takes seven pivots although the optimum is directly adjacent to the starting point. The same Klee-Minty cube in dimensions has inequalities and vertices of a polytope. On its lower last-coordinate face, increasing means increasing , and the first coordinates follow the corresponding lower-dimensional path before the last-coordinate facet can be left. On the upper face, increasing means decreasing , and the smallest-index rule traverses that path in reverse. The reverse-path assertion follows by the same induction, interchanging maximization and minimization on each face. Hence the pivot count satisfies , , and
The usual Bland pivoting rule prevents cycling, including degenerate pivots, but this exponential example shows that it does not give a polynomial worst-case pivot bound. For rational fixed , the constraints have polynomial encoding length. Arithmetic cost per pivot does not remove the exponential obstruction.
For a lower bound that applies to every pivot choice, use and maximize , starting at the origin. Each edge of this cube changes only one coordinate, whereas the unique optimal vertex of a polytope is . Every coordinate must therefore be changed along at least one edge. Every route of adjacent pivots takes at least pivots, and every strictly improving route takes exactly .
For Dantzig pivot rule, the rate is the objective increase per unit entering nonbasic variable, as in standard reduced cost pricing. Rescale the three coordinates by
The transformed linear program still maximizes , now with bounds
When the active facet for coordinate is freed, the other active equations give . The positive rates per unit are therefore
for , respectively. Equivalently, use the nonnegative lower- and upper-bound slack variables of these displayed, normalized inequalities: freeing coordinate changes its entering slack by . Thus Dantzig pivot rule chooses the lowest coordinate index among improving edges and follows the same seven-pivot path. In dimensions set ; the rates give the same pivots. These statements concern coordinate/slack pricing, not objective increase per unit Euclidean edge length, which defines a different pivot rule.
Let be shipments, with column sums eight and row sums at most the four capacities. Total demand is , below total capacity , so unused capacity is allowed. This is a transportation problem with capacity inequalities; equivalently add a dummy shop demanding four units with zero shipping cost.
Using the original PDF's cost , take the feasible solution
Its row totals are and all column totals are eight. Four units of capacity remain unused at the second factory. Its shipping cost is .
To prove that the cost is a global minimum, use the transportation dual certificate with capacity inequalities. If row potentials satisfy and , every feasible solution satisfies
where . The second inequality uses the sign of : multiplying a capacity upper bound by a nonpositive number reverses it. Choose and . The reduced costs are
so every entry is nonnegative. The lower bound is , equal to the displayed shipping cost. The minimum shipping cost is .
For the production costs in a transportation problem, add the production cost of each factory to every real shipment from that factory. Unused capacity incurs no production cost, so the dummy-shop costs remain zero. The resulting real-shop cost matrix is
A feasible solution is
Its row totals are and column totals remain eight, leaving four units unused at the fourth factory. Its combined cost is .
For a matching transportation dual certificate with capacity inequalities, take and . Their reduced costs are
all nonnegative. The lower bound is . Thus the minimum combined production and shipping cost is , and the second allocation attains it.
Use the transportation simplex algorithm, with transportation dual potentials and reduced costs . On a basic cell choose . The initial shipment matrix, read from the circled entries in the PDF, is
Its six positive cells form a transportation spanning tree. Setting gives
Enter cell , whose reduced cost is . The cycle pivot has signs
The maximum feasible increment is , so cell leaves the basis. The result is
For the new transportation spanning tree,
Enter cell with reduced cost . Its cycle pivot is
Now , and cell leaves. We obtain
Its row sums are and its column sums , as required. The final transportation dual potentials are
All reduced costs are nonnegative, proving optimality. More explicitly, for any feasible shipment matrix ,
Our shipments use only zero-reduced-cost cells and attain this lower bound. This supplies an independent weak duality certificate for the transportation optimum.
Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply and agent vertices demand . An arc from job to agent has cost and nonnegative flow ; an upper bound may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem is
Integer supplies and demands give an integral optimum by integrality of the transportation problem. Its positive arcs form a perfect matching, hence give one job per agent.
A network simplex algorithm basis for this connected -vertex network has tree arcs, whereas an integral assignment has only positive flows. For , at least 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 . For every feasible assignment ,
If the selected assignment uses only arcs with , its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by ; the TeX aid mistakenly replaces it with .
The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where . Search for an augmenting path in a matching in this equality graph. If there is none, let be the reachable jobs and the reachable agents in the alternating search from unmatched jobs. Every agent in is matched to a job in . Set
Reduced costs from to its complement decrease by , those from outside into 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 and . The reduced cost matrix is
Match job to agent . Searching from both unmatched jobs gives and ; the minimum cost to an agent outside is . Update to and :
The new equality edge augments the matching. From unmatched job , the next alternating search reaches agent and its matched job , giving and . Now . The updated feasible assignment dual potentials and reduced costs are
The augmenting path in a matching uses job to agent , the reversed matched edge to job , then the new edge to agent . It gives the optimal assignment
The dual linear program value is , an independent optimality certificate.
The stated plan is
Its six positive cells form a spanning tree of the supplier--consumer bipartite graph, so it is basic and feasible. Taking , the basic-cell equations give
The complete matrix of reduced costs is
The negative entry proves that the plan is not optimal.
Enter cell . The alternating cycle is
and the step is . The new plan is
whose cost is , down from . New potentials are
and the reduced-cost matrix is
Every reduced cost is nonnegative, so the transportation optimality criterion shows that
The zero reduced cost in cell also indicates an alternative optimum.
The northwest-corner rule constructs an initial basic feasible solution: fill the current cell with the smaller remaining supply and demand, delete the exhausted row or column, and continue.
For a current spanning-tree basis, solve on its occupied cells, fixing one potential to zero. The reduced cost of an unoccupied cell is
If all reduced costs are nonnegative, part (a) proves optimality. Otherwise choose a cell with negative reduced cost. Adding its edge to the tree creates a unique even cycle. Mark its cells alternately and , starting with at the entering cell, and set
Add on the plus cells and subtract it on the minus cells. Row and column totals are unchanged, the entering cell becomes positive, and a minimizing minus cell leaves the basis. In the nondegenerate case the objective decreases strictly. There are finitely many bases, so no basis repeats and the algorithm terminates at a basis with no negative reduced cost, which is optimal.
Changing only the second profit coefficient leaves the dual prices at , because the basic products remain one and three. The nonbasic product has nonpositive reduced cost exactly when . Therefore
There is no mathematical lower bound; if profit coefficients are additionally restricted to be nonnegative, intersect this range with . At , alternate optimal solutions are possible.
At the current dual prices , the new product has reduced cost , so it can increase profit. Its transformed resource column is
Increasing by changes the old basic variables to and . Thus leaves at , giving
For a certificate, take dual prices . They price the four products at , respectively, each at least its profit. Their resource total is , equal to the achieved profit. Weak duality proves optimality, and the profit has increased by two.