Linear programming

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

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.

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.

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.

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$.

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.

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

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

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.

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 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.

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

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.

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 $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.