Linear programming

Linear programming optimizes a linear function subject to finitely many linear equalities and inequalities.

An equality representation of a linear program in which each basic variable and the objective function are expressed using nonbasic variables, and all variables are nonnegative. Introducing slack variables into $Ax\le b$ gives $s=b-Ax$. Setting the nonbasic variables to zero yields its basic solution; nonnegative resulting basic values make this a basic feasible solution. A simplex algorithm pivot exchanges a basic and nonbasic index and rewrites these expressions.

Remove the integrality requirements from an integer program while retaining its linear inequalities and variable bounds. Every original feasible point remains feasible. Thus the relaxed optimum is an upper bound for a maximization problem and a lower bound for a minimization problem. An optimal relaxed feasible point need not have integer coordinates. Variable bounds that were implied only by an informal declaration such as binary must be made explicit before removing integrality.

This convention for standard maximum form of a linear program requires a maximizing linear function, upper-bound linear inequalities, and nonnegative variables. An unrestricted variable becomes the difference of two nonnegative variables; a lower-bound inequality changes sign. The corresponding dual linear program is $\min \{b^{T}y:A^{T}y\ge c,y\ge 0\}$. Adding nonnegative slack variables instead gives the equivalent equality-constraint standard form. Since standard-form terminology varies, state the chosen convention.

This form of linear programming additionally has the uniform vector as a strictly positive feasible point and known optimum zero. A homogeneous self-dual embedding of a linear program, followed by elimination of unrestricted Lagrange multipliers and normalization by the sum of nonnegative coordinates, yields this form without presupposing feasibility of the original program. The known start and optimum support projective interior-point methods. Polynomial bit-complexity statements additionally require finite rational input encoding; bounded arbitrary real coefficients alone do not provide it.

A surplus variable converts a lower-bound inequality $a^{T}x\ge b$ into $a^{T}x-z=b$, with $z\ge 0$. This is the lower-bound counterpart of a slack variable. When the original coefficients, right-hand side and decision variables are integer, the surplus variable is integer as well; that fact permits it to appear in an all-integer Gomory fractional cut row.

The set of minimizers of a linear objective on a linear polyhedron. It is a face: if a strict convex combination of two feasible points minimizes the objective, both points must also minimize it. Hence an extreme point of an optimal face is an extreme point of the original polyhedron. Successively minimizing further linear objectives restricts to nested faces, whose vertices remain original vertices. This preserves uniform rational denominator bounds in exact feasibility-oracle optimization.

A nonempty linear polyhedron with integer inequality coefficients and right sides bounded by $U\ge 1$ contains a point $x_i=p_i/q_i$ with the displayed bounds. Intersect with an orthant containing a feasible point. Moving along directions annihilating the active constraints, until another constraint becomes active, produces a vertex: the orthant prevents a whole nontrivial line from remaining feasible. At that vertex, choose $n$ independent active inequalities, including coordinate constraints as necessary. Cramer's rule and the Hadamard determinant inequality bound both determinants by $n^{n/2}{U}^n\le (nU{)}^n$. The resulting rational witness has polynomial binary length and is verifiable in polynomial time, proving that integer linear feasibility is in NP.

The ellipsoid method repeatedly asks a separation oracle about the center of a containing ellipsoid and replaces that ellipsoid by a smaller one containing its intersection with a separating half-space. The volume decreases by a dimension-dependent factor at each iteration. For rational polyhedra, the exact feasibility theorem has polynomial bit complexity in the dimension and coefficient encoding bounds when separation is polynomial time. It includes lower-dimensional feasible sets through rational precision bounds or suitable relaxations; one must not declare infeasibility just because the original feasible set has zero volume.

A nonempty linear polyhedron can have no extreme point. Intersect it with an orthant containing one feasible point, and minimize the sum of the signed coordinates there. The relevant sublevel sets are compact, so the minimum face has an extreme point, which is also extreme in the orthant intersection. The added signed-coordinate rows are integer rows with entries at most one. The integer-matrix vertex coordinate bound gives $R=n!\max (1,U{)}^n$. This supplies a bounded feasibility search even when the original polyhedron contains lines.

For an integer linear polyhedron $P=\{x\in {\mathbb{R}}^n:Ax\ge b\}$ with coefficients bounded by $U\ge 1$, put $D=[(n+1)U{]}^{n+1}$ and $0<\epsilon <1/D$. If $x_0\in P$, every $h$ with $\Vert h{\Vert }_2\le \epsilon /(nU)$ satisfies $A_{i}h\ge -\sqrt{n}U\Vert h{\Vert }_2\ge -\epsilon$. Thus $P_{\epsilon }$ contains a positive-radius Euclidean ball and is a full-dimensional linear polyhedron. If $P$ is empty, the normalized integer Farkas infeasibility gap gives $\lambda \ge 0$, $A^T\lambda =0$, $1^T\lambda =1$ and $b^T\lambda \ge 1/D$. A point of $P_{\epsilon }$ would give $0={\lambda }^{T}Ax\ge b^T\lambda -\epsilon >0$, a contradiction. Consequently this relaxation preserves emptiness and supplies the inner-volume bound needed by the ellipsoid method, even when $P$ has empty interior.

A polynomial-time algorithm for integer linear feasibility gives exact rational linear programming optimization. Rational vertex bounds give a polynomial-bit bound on every finite optimal value and its denominator. An objective threshold below that bound detects unboundedness after feasibility is established. Binary search with the additional inequality $c^{T}x\le t$ localizes the finite optimum to an interval containing a unique rational of bounded denominator; continued fractions recover it exactly. A feasible optimizer can then be found by successive coordinate minimizations on a bounded optimal face. These produce faces of one fixed rational polytope, so one uniform vertex-denominator bound works throughout, avoiding exponential growth of precision requirements.

For $n\ge 2$, the standard ellipsoid covering a centrally cut half of the unit ball has center $e_1/(n+1)$ and shape matrix $D^{\prime }=\frac{n^2}{n^2-1}(I-\frac{2}{n+1}{e}_1{e}_1^T)$. Its eigenvalues are $n^2/(n+1{)}^2$ along $e_1$ and $n^2/(n^2-1)$ in the other directions. Hence its volume ratio is $R=\frac{n}{n+1}(\frac{n^2}{n^2-1}{)}^{(n-1)/2}$. Using $\log (1-a)<-a$ and $\log (1+b)<b$ gives $\log R<-1/(2(n+1))$. Affine changes of coordinates preserve the volume ratio. The resulting geometric convergence underlies the ellipsoid method; exact rational feasibility additionally needs input-dependent size, precision and lower-dimensional feasibility bounds.

Given finitely encoded linear inequalities, a maximum feasible subsystem is a largest collection that can be simultaneously satisfied. Its decision version asks whether some $k$ inequalities admit a common solution. This is NP-complete, despite polynomial time feasibility testing for each fixed collection. For a graph, use nonnegative variables $x_v$, constraints $x_v\ge 1$ for vertices, and $M>|V|$ copies of $x_u+x_v\le 1$ for each edge. A subsystem of size $M|E|+k$ must retain a copy of every edge constraint and at least $k$ vertex constraints; those vertices form an independent set. Conversely an independent set of size $k$ supplies such a feasible subsystem by its indicator vector.

A linear polyhedron is an intersection of finitely many closed affine half-spaces in finite-dimensional real space. It may be empty, unbounded, or lower-dimensional. This usage differs from a three-dimensional geometric polyhedron. The strict separation of disjoint linear polyhedra follows from linear programming duality.

For a linear polyhedron $P=\{x\in {\mathbb{R}}^n:Ax\le b\}$, a vertex of a linear polyhedron is a feasible point $p$ at which the normals of the active constraints span ${\mathbb{R}}^n$. Equivalently, $n$ linearly independent active constraints uniquely determine $p$. A linear polyhedron may be unbounded or lower-dimensional; the definition applies in those cases as well as to a convex polytope.

Such a point is an extreme point. Indeed, if $p=\lambda u+(1-\lambda )v$ with $u,v\in P$ and $0<\lambda <1$, every active constraint at $p$ must also be an equality at $u$ and $v$. Selecting $n$ independent active rows forces $u=v=p$. Conversely, if the active normals do not span ${\mathbb{R}}^n$, take a nonzero vector $h$ annihilated by all active rows. The finitely many inactive inequalities have positive slack, so both $p+\epsilon h$ and $p-\epsilon h$ remain feasible for sufficiently small $\epsilon >0$. Their midpoint is $p$, so $p$ is not an extreme point. Thus these notions coincide for a linear polyhedron.

A linear polyhedron in ${\mathbb{R}}^n$ is full-dimensional when its affine hull is all of ${\mathbb{R}}^n$. Equivalently, it contains an open Euclidean ball. An open Euclidean ball spans the ambient space. Conversely, a full-dimensional convex set contains $n+1$ affinely independent points; their convex hull is a simplex with nonempty interior, so the set contains an open Euclidean ball.

An inequality constraint which holds with equality at the point under consideration. For $Ax\ge b$, a direction annihilating every active row permits sufficiently small feasible moves of either sign. If the active rows have rank $n$, their common solution is a basic feasible solution; the independent equalities uniquely determine it.

At an extreme point of $\{x:Ax\ge b\}$, the active rows span the ambient dimension: otherwise a nonzero direction orthogonal to all active rows permits small feasible moves of both signs. Select $n$ independent active rows to form an integer matrix $B$. Its nonzero determinant has absolute value at least one. Cramer's rule and the determinant expansion bound each coordinate by $n!U^n$, where $U$ bounds the entries of $A$ and $b$. The vector $b$ may be real; only the denominator matrix needs to be integer.

Nonempty disjoint linear polyhedra $P=\{x:Ax\le b\}$ and $Q=\{y:Cy\le d\}$ admit $h$ with a strictly positive separation gap. A phase-I linear program minimizing common constraint violation has positive attained optimum. Its Lagrangian dual problem gives nonnegative $\lambda ,\mu$ with $A^T\lambda +C^T\mu =0$ and ${\lambda }^{T}b+{\mu }^{T}d<0$. Then $h=A^T\lambda$ satisfies $h^{T}x\le {\lambda }^{T}b<-{\mu }^{T}d\le h^{T}y$. The polyhedral hypothesis matters; arbitrary disjoint closed convex sets need not have a positive separation gap.

A slack variable turns an inequality constraint $a^{T}x\le b$ into the equality $a^{T}x+s=b$ with $s\ge 0$. Its value measures the unused amount of the constraint. In the simplex algorithm, slack variables often supply the initial basic feasible solution.

For $f$ of degree $d$ and $n\ge \max (1,d)$, compute its degree-$n$ Bernstein basis coefficients and solve $\max \lambda$ subject to $\lambda \le {\beta }_{k,n}$, $0\le k\le n$. This is a linear program with $n+1$ inequalities. The coefficients form a convex-combination enclosure of the polynomial values, so $v_n\le \min f$. Degree elevation of Bernstein coefficients makes the bounds monotone. For every $ϵ>0$, the polynomial $f-(\min f-ϵ)$ is strictly positive, so positive Bernstein coefficients for a strictly positive polynomial gives an eventual feasible bound $\min f-ϵ$. Hence $v_n$ converges to the true minimum. Earlier indices $n<d$ can use a one-inequality program at any common coefficient-based lower bound, preserving the stated constraint count for every positive index.

For $Ax=b$, $x\ge 0$, a feasible vector $x$ is basic when the columns $A_i$ indexed by its positive coordinates are linearly independent. Equivalently, enlarge those columns to a basis, set every nonbasic coordinate to zero, and solve the resulting square system.

A basic feasible solution is degenerate when one or more of its basic variables is zero. A simplex algorithm pivot may then change the basis without moving the feasible point or changing the objective. Assignment networks force many zero-flow basic tree arcs.

For a full-row-rank system $Ax=b$ with $m$ rows, choose $m$ linearly independent columns, set all remaining variables to zero, and solve the resulting square system. The resulting vector is a basic solution; it is feasible when it also satisfies the required nonnegativity constraints.

If a linear program has an optimal solution, it has an optimal basic feasible solution. Choose an optimum with minimal positive support. A dependence among its active columns gives a feasible two-sided perturbation; optimality makes its objective slope zero, and moving until one coordinate vanishes contradicts minimality.

Linear-fractional programming optimizes a ratio $c^{T}x/d^{T}x$ over a polyhedron on which the denominator is positive.

For $d^{T}x>0$, setThen $d^{T}y=1$, and $Ax=b$ becomes $Ay=bt$, turning a linear-fractional program into a linear program with objective $c^{T}y$.

Every linear maximization program has a dual minimization program whose feasible objective values bound the primal values.

For minimization with constraints $Ax=b$, $x\ge 0$, a dual-feasible vector $y$ obeys $A^{T}y\le c$, so $b^{T}y$ is a lower bound on every primal-feasible objective value. For a simplex dictionary with basis matrix $B$, the associated vector is $y^T=c_B^T{B}^{-1}$. Its basic reduced costs are zero and its nonbasic reduced costs are $c_N^T-c_B^T{B}^{-1}{A}_N$. 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.

Minimizing ${\max }_i(a_i^{T}x+b_i)$ over unrestricted $x$ is a linear program after introducing an epigraph variable $t$ and inequalities $a_i^{T}x+b_i\le t$. Its optimization Lagrangian has finite infimum over $x,t$ exactly when the nonnegative multipliers sum to one and their weighted slopes sum to zero. The displayed Lagrangian dual problem maximizes the resulting constant lower bound. It identifies the role of a zero-slope convex combination of the affine functions.

For a minimization problem with inequalities $g_i(x)\le 0$, the Lagrangian is $L(x,\lambda )=f(x)+{\sum }_i{\lambda }_i{g}_i(x)$ with ${\lambda }_i\ge 0$. The Lagrangian dual maximizes the concave dual function $q(\lambda )={\inf }_{x}L(x,\lambda )$.

The Lagrange dual function is the infimum of a Lagrangian over its primal variables. It is concave in the multipliers, even before convexity of the primal problem is assumed. Maximizing it over sign-compatible multipliers gives a lower bound on a minimization problem by weak duality; appropriate convex qualifications give strong duality.

A Lagrangian relaxation moves selected constraints into the objective with appropriately signed Lagrange multipliers. Maximizing the relaxed objective over a larger easy set gives an upper bound for a constrained maximization problem. Optimizing that bound need not solve the original integer problem.

Retaining integer assignment equations while dualizing extra capacity inequalities gives an easily evaluated upper bound for a maximization problem. With multipliers $\lambda \ge 0$ and capacities $b$, it is $\theta (\lambda )={\max }_{x\text{ assignment}}[c^{T}x+{\lambda }^T(b-Ax)]$. It is a convex maximum of affine functions. Minimizing it exploits the convex hull of assignments, so it can have a finite optimum when only a fractional mixture satisfies the side constraints and no integer assignment does. This separates a useful relaxation bound from a certificate of integer feasibility.

For binary knapsack optimization, $U(\lambda )$ is an upper bound for every $\lambda \ge 0$. Its minimum is computable from the finitely many profit-to-weight breakpoints and agrees with the fractional knapsack problem optimum. Zero-weight positive-profit terms are added independently.

For a primal maximization problem $Ax\le b$, $x\ge 0$, the dual minimizes $b^{T}y$ subject to $A^{T}y\ge c$, $y\ge 0$.

A dual variable is a multiplier associated with a primal constraint in a dual linear program. In a minimization linear program with equality constraints $Ax=b$ and nonnegative primal variables, the Lagrangian $c^{T}x+y^T(b-Ax)$ yields the dual objective $b^{T}y$ and inequalities $A^{T}y\le c$; the equality-constraint multipliers $y$ are unrestricted in sign. For a transportation problem, row and column dual variables give potentials $u_i,v_j$ satisfying $u_i+v_j\le c_{ij}$. Complementary slackness makes occupied routes attain equality.

The dual pairsatisfies weak duality because $b^{T}y\le y^{T}Ax=x^T{A}^{T}y\le c^{T}x$ for every feasible pair.

Every feasible dual objective value bounds every feasible primal objective value.

For the linear program maximizing $c^{T}x$ with $Ax\le b$, $x\ge 0$, a vector $y\ge 0$ with $A^{T}y\ge c$ proves $c^{T}x\le y^{T}b$ for every feasible $x$. If a feasible $x$ attains that bound, it is optimal. This is weak duality written as a directly checkable certificate; adding nonnegative multiples of constraints suffices to verify it. The equivalent reversed-inequality certificate applies to a minimization program.

Strong duality means that the primal and dual optimal values are equal. It holds for every feasible bounded linear program and for broad classes of convex optimization problems under a constraint qualification.

A jointly proper convex function $f(x,z)$ represents an optimization problem at perturbation $z=0$ and a family of nearby problems at other $z$. Its primal value function is $p(z)={\inf }_{x}f(x,z)$. Relaxing an inequality by $z$ gives the example $f(x,z)=J(x)+{\delta }_{(-\infty ,0]}(r(x)-\sigma -z)$, using an indicator functional. The resulting convex perturbation duality expresses multipliers as supporting subgradients of the value function.

For a convex perturbation function, defineThe primal and dual values are $p(0)$ and $q(0)$; the signed dual marginal $q$ is concave. The identity $p^{\ast }(y)=f^{\ast }(0,y)$ gives $q(0)=p^{\ast \ast }(0)$. If $p$ is proper and finite near zero, subgradients at zero prove strong duality with dual attainment. In finite dimensions the relative-interior condition $0\in \mathrm{ri}(\mathrm{dom}p)$ also suffices, provided $p(0)$ is finite. This does not itself prove primal attainment.

An optimal dual variable $y^{\ast }\in \partial p(0)$ bounds the effect of perturbing a convex value function:If $p$ is finite convex near zero, $p^{\prime }(0;d)={\max }_{y\in \partial p(0)}⟨y,d⟩$. A singleton subdifferential gives differentiability and a first-order expansion. For an upper-bound constraint relaxed by $z$, the derivative equals the negative of the nonnegative Lagrange multiplier; relaxing the bound can decrease the minimum value.

The Slater condition requires a feasible point at which every nonlinear convex inequality is strict and every affine equality holds. For a convex problem it implies strong duality and attainment of the dual optimum under standard finiteness assumptions.

An exact maximum-violation penalty replaces inequalities $g_i(x)\le 0$ by the unconstrained objective $f(x)+M\max (0,g_1(x),\dots ,g_m(x))$. If an optimal dual multiplier is ${\lambda }^{\ast }$, every $M>\Vert {\lambda }^{\ast }{\Vert }_1$ makes every penalized minimizer feasible and optimal.

Dual attainment means that a feasible choice of Lagrange multipliers achieves the optimal value of the Lagrangian dual problem. Equality of primal and dual optimal values alone does not imply dual attainment.

For finite primal and dual optimal values in a minimization problem, the duality gap is $p_{\ast }-d_{\ast }\ge 0$. Strong duality means this difference is zero.

At a primal-dual optimum, each positive variable corresponds to a tight dual constraint and conversely for positive dual variables.

For the linear program maximizing $c^{T}x$ subject to $Ax=b$, $x\ge 0$, let $x^{\ast }$ be optimal and let $y^{\ast }$ be an optimal dual linear program solution. Complementary slackness makes $A_j^T{y}^{\ast }=c_j$ on every positive coordinate of $x^{\ast }$. Any nonnegative $\hat{x}$ supported on those coordinates therefore hasThe same $y^{\ast }$ is dual feasible when the right-hand side is changed to $\hat{b}=A\hat{x}$. Equality of feasible objectives and weak duality prove optimality of $\hat{x}$ for that modified problem.

There is also a direct primal proof. If $z\ge 0$ had $Az=A\hat{x}$ and $c^{T}z>c^T\hat{x}$, then $x^{\ast }+\epsilon (z-\hat{x})$ would remain feasible and nonnegative for sufficiently small $\epsilon >0$. On zero coordinates of $x^{\ast }$, support inclusion makes its perturbation nonnegative; on positive coordinates, smallness preserves positivity. Its objective would improve, contradicting optimality of $x^{\ast }$.

For the primal linear program maximising $c^{T}x$ with $Ax\le b$, $x\ge 0$, and its dual linear program minimising $b^{T}y$ with $A^{T}y\ge c$, $y\ge 0$, let $x,y$ be optimal. The complementary slackness identity gives $x_j((A^{T}y{)}_j-c_j)=0$. Thus a strict inequality in the $j$th dual constraint forces $x_j=0$. One optimal dual feasible solution can therefore force zero components in every primal optimum. The same argument with roles reversed says that $y_i>0$ forces the $i$th primal constraint to be an equality.

The transportation problem minimizes linear shipping cost while matching prescribed row supplies and column demands.

This is the finite discrete optimal transport problem with prescribed supply and demand marginals.

When factory $i$ incurs unit production cost $p_i$ only on goods actually shipped, add that cost to every real shipping destination in its row. Unused capacity incurs no production cost; a dummy unused-capacity column therefore keeps zero cost rather than receiving $p_i$. This changes the optimal factory utilization when capacity exceeds total demand. Transportation dual certificate with capacity inequalities proves optimality without assuming every factory must produce at full capacity.

Row and column potentials satisfying the displayed inequalities give a lower bound on the cost of every feasible shipment matrix: ${\sum }_{ij}{c}_{ij}{x}_{ij}\ge {\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$, since row sums are supplies $s_i$ and column sums are demands $d_j$. The reduced costs are $c_{ij}-u_i-v_j$. A feasible matrix using only zero-reduced-cost cells attains the lower bound, proving optimality by weak duality. The transportation simplex algorithm sets these potentials by equality on a transportation spanning tree, and enters a negative-reduced-cost cell if one exists.

For shipments $x_{ij}\ge 0$ with factory row sums at most capacities $s_i$ and shop column sums exactly demands $d_j$, the displayed dual potentials give $\sum c_{ij}{x}_{ij}\ge {\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$. The sign $u_i\le 0$ ensures $u_i{\sum }_j{x}_{ij}\ge u_i{s}_i$. Equality proves optimality. It occurs when every used cell is tight and every row with spare capacity has $u_i=0$, the relevant complementary slackness conditions. A dummy demand column with zero costs converts unused capacity into a balanced transportation problem.

The assignment problem chooses a one-to-one pairing of jobs and agents minimizing their total cost. Its minimum-cost flow formulation puts unit supplies on job vertices and unit demands on agent vertices of a bipartite graph. Integral feasible flows are perfect matchings.

For a partial assignment problem, add its fixed cost to the sum, over remaining tasks, of each task's cheapest available machine cost. This is a lower bound because it relaxes the requirement that different tasks use distinct machines. It is an admissible bound for branch and bound, even though the minimizing choices may assign the same machine repeatedly.

// Target: mathematical-optimization.bigb

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.

These feasible potentials give the lower bound ${\sum }_i{\lambda }_i-{\sum }_j{\mu }_j$ on every assignment cost. An assignment using only equality edges attains this bound and is optimal by weak duality and complementary slackness.

The transportation polytope is the set of nonnegative matrices with fixed row and column sums.

The positive cells of a nondegenerate transportation basis form a spanning tree in the bipartite graph of supply and demand vertices.

The transportation simplex computes row and column potentials, enters a negative-reduced-cost cell, and pivots around its induced alternating cycle.

The northwest-corner method repeatedly allocates the smaller remaining supply and demand in the current top-left cell to construct an initial transportation basis.

For transportation potentials, the reduced cost is ${\bar{c}}_{ij}=c_{ij}-u_i-v_j$; a negative value identifies an improving entering cell.

Adding a nonbasic edge to a transportation tree creates one cycle; alternating equal additions and subtractions around it preserves every row and column sum.

Integer supplies and demands admit an integer optimum because an integer initial basis and every cycle pivot remain integer.

A matrix of nonnegative rational numbers with integer row and column sums can be rounded entrywise up or down while preserving all those sums. Let $p_{ij}=\lfloor a_{ij}\rfloor$ and $f_{ij}=a_{ij}-p_{ij}$ be its floor and fractional part. The residual row and column sums $r_i={\sum }_j{f}_{ij}$ and $c_j={\sum }_i{f}_{ij}$ are nonnegative integers. Build a flow network with source-to-row flow network edge capacities $r_i$, row-to-column flow network edge capacities one where $f_{ij}>0$, and column-to-sink flow network edge capacities $c_j$. The fractional parts supply a feasible flow saturating all source arcs. The integral max-flow theorem supplies an integral one of the same total value. If its middle-arc flows are $h_{ij}\in \{0,1\}$, with $h_{ij}=0$ where $f_{ij}=0$, then $b_{ij}=p_{ij}+h_{ij}$ is the required matrix. This is a constructive polynomial-time algorithm; no multiplication by a common denominator is required.

A matrix is totally unimodular when every square subdeterminant is $0$, $1$, or $-1$; linear programs with such a constraint matrix and integer right side have integral vertices.

A matrix with entries in $\{0,1,-1\}$ is a totally unimodular matrix if every column has at most two nonzero entries, with opposite signs when both occur. To prove this, induct on the size of a square submatrix. A zero column gives determinant zero, a one-entry column reduces by cofactor expansion, and if every column has two entries then all column sums vanish, giving dependent rows. The total unimodularity of directed incidence matrices is a central instance.

The directed vertex-edge incidence matrix has one $+1$ and one $-1$ per nonloop column and a zero column for a loop. Every square subdeterminant belongs to $\{0,1,-1\}$. Induct on its size: a column with no nonzero entries makes the determinant zero; a column with one nonzero entry permits a cofactor expansion to a smaller determinant; and if every column has two nonzero entries, their opposite signs make the column sums zero, giving linearly dependent rows. Negating rows preserves absolute subdeterminants. Consequently the unsigned vertex-edge incidence matrix of a bipartite graph is totally unimodular: negate all rows in one part. The assignment problem is an instance, with row vertices and column vertices forming the two parts.

The simplex method moves between adjacent basic feasible solutions along improving edges of a feasible polytope until no improving pivot remains.

In a feasible minimization simplex dictionary, the nonbasic variables are nonnegative. If every reduced cost ${\bar{c}}_j\ge 0$, the displayed objective identity proves $z\ge z_0$ for every feasible point. Thus the current basic feasible solution is globally optimal. If all reduced costs are strictly positive, equality forces every nonbasic variable to vanish and gives a unique basic solution, provided the dictionary determines all basic variables.

For a feasible simplex dictionary, let $r_j>0$ be a nonbasic variable's improving reduced cost and let ${\theta }_j$ be its largest feasible increase from the simplex ratio test. The greatest improvement pivot rule chooses an entering variable maximizing $r_j{\theta }_j$. It measures the improvement over the entire edge, whereas the Dantzig pivot rule maximizes only $r_j$.

// Target: mathematical-optimization.bigb

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 $2^n-1$-pivot path as smallest-index improving-facet pivoting.

For $0<\epsilon <1/2$, these inequalities define a deformed cube with $2^n$ vertices of a polytope. Choose either the lower or upper bound recursively at each coordinate to obtain a vertex of a polytope; changing one choice gives an adjacent vertex of a polytope. When maximizing $x_n$, smallest-index improving-facet pivoting visits all $2^n$ vertices of a polytope: first traverse the lower last-coordinate face, then move to the upper face and traverse the preceding path in reverse. Thus this geometric version of the Bland pivoting rule can require $2^n-1$ pivots. Rescaling the coordinate $x_i$ to $y_i={\epsilon }^{2(n-i)}{x}_i$ makes the positive rate per unit freed coordinate equal to ${\epsilon }^{-(n-i)}$; Dantzig pivot rule then selects the same exponential path. Euclidean edge-length pricing is a different rule.

A simplex tableau records the canonical constraint equations for a simplex basis and the canonical objective equation. For maximization use $z+{\sum }_j{\rho }_j{x}_j=z_0$, so a negative nonbasic objective-row coefficient is an improving direction. Constraint rows have an identity matrix in the basic columns. A simplex method pivot divides the leaving row by the pivot coefficient and eliminates the entering column from the other rows, including the objective row. The simplex ratio test chooses the largest feasible step. When all basic values and all ${\rho }_j$ are nonnegative, the objective equation directly proves $z\le z_0$ for every nonnegative feasible vector.

For a maximization problem with unpriced unit slack variables, their columns in a final simplex tableau give $B^{-1}$, where $B$ consists of the original basic columns. The constraint right side is $\bar{b}=B^{-1}b$, so $b=B\bar{b}$. If the objective row uses reduced costs $r_j=c_j-c_B^T{B}^{-1}{A}_j$, its slack entries are $-y^T$ with $y^T=c_B^T{B}^{-1}$. Therefore $c_B^T=y^{T}B$. In a homogeneous linear objective with no constant offset, the displayed basic objective value must equal $c_B^T\bar{b}=y^{T}b$. This identity detects inconsistent tableau constants; an affine offset affects the value but not the reduced costs.

If a variable $x_k$ gains an objective coefficient $p$, the new objective is $z=z_{\mathrm{old}}+p{x}_k$. Substitute this in the old canonical objective equation and eliminate any remaining basic-column coefficients using the constraint rows. If $x_k$ is nonbasic, this simply subtracts $p$ from its objective-row coefficient. When a slack variable is sold, rename the old slack as the sales quantity; its equation already gives the correct equality and no new slack is added. Reoptimization can then start directly from the altered simplex tableau.

For a maximization simplex dictionary, choose the smallest-index nonbasic variable with positive reduced cost to enter. Among basic variables attaining the minimum feasible ratio, choose the smallest-index one to leave. This fixed index rule prevents cycling, including in degenerate pivots whose step length is zero. It need not minimize the number of pivots on a particular instance.

Phase I introduces nonnegative artificial variables to create a feasible basis and minimizes their sum, or maximizes its negative. A positive minimum proves infeasibility. At a zero minimum, remove artificial variables and use the resulting feasible original basis in Phase II with the original objective. If an artificial variable remains basic at zero, pivot it out when possible; otherwise its row is redundant. Each phase uses the simplex ratio test to preserve nonnegative basic values.

In a feasible simplex basis, increasing a nonbasic variable by $\theta$ changes basic coordinates to $x-\theta d$. Nonnegativity limits $\theta$ by the smallest ratio $x_i/d_i$ with $d_i>0$; a minimizing coordinate leaves the basis. Ties can leave zero-valued basic variables. This pivot test is distinct from the analytic ratio test for series convergence.

For standard-form linear programming constraints $Ax=b$ of full row rank, a simplex basis is a set of columns forming an invertible square matrix $B$. The remaining variables are nonbasic; setting them to zero gives the basic solution $x_B=B^{-1}b$. It is feasible if these basic variables are nonnegative. A pivot exchanges one basic and one nonbasic column while maintaining this representation.

A nonbasic variable corresponds to a column outside the current simplex basis. In standard nonnegative linear programming, it is set to zero at the basic solution. With explicit finite bounds, it is normally fixed at one of its bounds.

// Target: mathematical-optimization.bigb

A basic variable corresponds to a column of the current simplex basis. Given the nonbasic variables, the invertible basis matrix determines the basic variables from the equality constraints.

// Target: mathematical-optimization.bigb

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 $A_B^{-1}(b+ϵ)$, and the objective is the displayed affine function, with $y$ 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.

For a square invertible constraint matrix $A$ in $\max \{c^{T}x:Ax\le b,x\ge 0\}$, suppose $y>0$ and $A^{T}y=c$. This fixed dual vector stays optimal under a changed right-hand side $b^{\prime }$ exactly when $A^{-1}{b}^{\prime }\ge 0$. Sufficiency follows from primal feasibility and equal primal/dual objectives. Necessity follows from complementary slackness: since every $y_i$ is positive, every optimal primal constraint must bind, forcing $x=A^{-1}{b}^{\prime }$. The inequalities define the whole validity cone, including degenerate boundary optima.

For $0\le x_i\le 1$, $x_1+x_2+x_3\le 5/2$, and objective $x_1+2x_2+4x_3$, the oriented edge graph has eight improving paths from the origin to the unique optimum $(1/2,1,1)$. Their lengths range from three to five pivots.