Linear programming

Suppose that a farmer has a piece of farm land, say L km², to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, F kilograms, and pesticide, P kilograms. Every square kilometer of wheat requires F₁ kilograms of fertilizer and P₁ kilograms of pesticide, while every square kilometer of barley requires F₂ kilograms of fertilizer and P₂ kilograms of pesticide. Let S₁ be the selling price of wheat per square kilometer, and S₂ be the selling price of barley. If we denote the area of land planted with wheat and barley by x₁ and x₂ respectively, then profit can be maximized by choosing optimal values for x₁ and x₂. This problem can be expressed with the following linear programming problem in the standard form:

Maximize: ${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(maximize the revenue (the total wheat sales plus the total barley sales) – revenue is the "objective function")
Subject to:	${\displaystyle x_{1}+x_{2}\leq L}$	(limit on total area)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}$	(limit on fertilizer)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}$	(limit on pesticide)
	${\displaystyle x_{1}\geq 0,x_{2}\geq 0}$	(cannot plant a negative area).

In matrix form this becomes:

maximize ${\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}$

subject to ${\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.}$

The example above is converted into the following augmented form:

Maximize: ${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(objective function)
subject to:	${\displaystyle x_{1}+x_{2}+x_{3}=L}$	(augmented constraint)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F}$	(augmented constraint)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P}$	(augmented constraint)
	${\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.}$

where ${\displaystyle x_{3},x_{4},x_{5}}$ are (non-negative) slack variables, representing in this example the unused area, the amount of unused fertilizer, and the amount of unused pesticide.

In matrix form this becomes:

Maximize ${\displaystyle z}$:

${\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.}$

A covering LP is a linear program of the form:

Minimize: b^Ty,

subject to: A^Ty ≥ c, y ≥ 0,

such that the matrix A and the vectors b and c are non-negative.

The dual of a covering LP is a packing LP, a linear program of the form:

Maximize: c^Tx,

subject to: Ax ≤ b, x ≥ 0,

such that the matrix A and the vectors b and c are non-negative.

Covering and packing LPs commonly arise as a linear programming relaxation of a combinatorial problem and are important in the study of approximation algorithms.[8] For example, the LP relaxations of the set packing problem, the independent set problem, and the matching problem are packing LPs. The LP relaxations of the set cover problem, the vertex cover problem, and the dominating set problem are also covering LPs.

Finding a fractional coloring of a graph is another example of a covering LP. In this case, there is one constraint for each vertex of the graph and one variable for each independent set of the graph.

Geometrically, the linear constraints define the feasible region, which is a convex polyhedron. A linear function is a convex function, which implies that every local minimum is a global minimum; similarly, a linear function is a concave function, which implies that every local maximum is a global maximum.

An optimal solution need not exist, for two reasons. First, if the constraints are inconsistent, then no feasible solution exists: For instance, the constraints x ≥ 2 and x ≤ 1 cannot be satisfied jointly; in this case, we say that the LP is infeasible. Second, when the polytope is unbounded in the direction of the gradient of the objective function (where the gradient of the objective function is the vector of the coefficients of the objective function), then no optimal value is attained because it is always possible to do better than any finite value of the objective function.

Otherwise, if a feasible solution exists and if the constraint set is bounded, then the optimum value is always attained on the boundary of the constraint set, by the maximum principle for convex functions (alternatively, by the minimum principle for concave functions) since linear functions are both convex and concave. However, some problems have distinct optimal solutions; for example, the problem of finding a feasible solution to a system of linear inequalities is a linear programming problem in which the objective function is the zero function (that is, the constant function taking the value zero everywhere). For this feasibility problem with the zero-function for its objective-function, if there are two distinct solutions, then every convex combination of the solutions is a solution.

The vertices of the polytope are also called basic feasible solutions. The reason for this choice of name is as follows. Let d denote the number of variables. Then the fundamental theorem of linear inequalities implies (for feasible problems) that for every vertex x^* of the LP feasible region, there exists a set of d (or fewer) inequality constraints from the LP such that, when we treat those d constraints as equalities, the unique solution is x^*. Thereby we can study these vertices by means of looking at certain subsets of the set of all constraints (a discrete set), rather than the continuum of LP solutions. This principle underlies the simplex algorithm for solving linear programs.

The simplex algorithm, developed by George Dantzig in 1947, solves LP problems by constructing a feasible solution at a vertex of the polytope and then walking along a path on the edges of the polytope to vertices with non-decreasing values of the objective function until an optimum is reached for sure. In many practical problems, "stalling" occurs: many pivots are made with no increase in the objective function.[9][10] In rare practical problems, the usual versions of the simplex algorithm may actually "cycle".[10] To avoid cycles, researchers developed new pivoting rules.[11]

In practice, the simplex algorithm is quite efficient and can be guaranteed to find the global optimum if certain precautions against cycling are taken. The simplex algorithm has been proved to solve "random" problems efficiently, i.e. in a cubic number of steps,[12] which is similar to its behavior on practical problems.[9][13]

However, the simplex algorithm has poor worst-case behavior: Klee and Minty constructed a family of linear programming problems for which the simplex method takes a number of steps exponential in the problem size.[9][14][15] In fact, for some time it was not known whether the linear programming problem was solvable in polynomial time, i.e. of complexity class P.

Like the simplex algorithm of Dantzig, the criss-cross algorithm is a basis-exchange algorithm that pivots between bases. However, the criss-cross algorithm need not maintain feasibility, but can pivot rather from a feasible basis to an infeasible basis. The criss-cross algorithm does not have polynomial time-complexity for linear programming. Both algorithms visit all 2^D corners of a (perturbed) cube in dimension D, the Klee–Minty cube, in the worst case.[11][16]

In contrast to the simplex algorithm, which finds an optimal solution by traversing the edges between vertices on a polyhedral set, interior-point methods move through the interior of the feasible region.

This is the first worst-case polynomial-time algorithm ever found for linear programming. To solve a problem which has n variables and can be encoded in L input bits, this algorithm runs in ${\displaystyle O(n^{6}L)}$ time.[5] Leonid Khachiyan solved this long-standing complexity issue in 1979 with the introduction of the ellipsoid method. The convergence analysis has (real-number) predecessors, notably the iterative methods developed by Naum Z. Shor and the approximation algorithms by Arkadi Nemirovski and D. Yudin.

Khachiyan's algorithm was of landmark importance for establishing the polynomial-time solvability of linear programs. The algorithm was not a computational break-through, as the simplex method is more efficient for all but specially constructed families of linear programs.

However, Khachiyan's algorithm inspired new lines of research in linear programming. In 1984, N. Karmarkar proposed a projective method for linear programming. Karmarkar's algorithm[6] improved on Khachiyan's[5] worst-case polynomial bound (giving ${\displaystyle O(n^{3.5}L)}$). Karmarkar claimed that his algorithm was much faster in practical LP than the simplex method, a claim that created great interest in interior-point methods.[17] Since Karmarkar's discovery, many interior-point methods have been proposed and analyzed.

In 1987, Vaidya proposed an algorithm that runs in ${\displaystyle O(n^{3})}$ time.[18]

In 1989, Vaidya developed an algorithm that runs in ${\displaystyle O(n^{2.5})}$ time.[19] Formally speaking, the algorithm takes ${\displaystyle O((n+d)^{1.5}nL)}$ arithmetic operations in the worst case, where ${\displaystyle d}$ is the number of constraints, ${\displaystyle n}$ is the number of variables, and ${\displaystyle L}$ is the number of bits.

In 2015, Lee and Sidford showed that, it can be solved in ${\displaystyle {\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)}$ time,[20] where ${\displaystyle nnz(A)}$ represents the number of non-zero elements, and it remains taking ${\displaystyle O(n^{2.5}L)}$ in the worst case.

In 2019, Cohen, Lee and Song improved the running time to ${\displaystyle {\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)}$ time, ${\displaystyle \omega }$ is the exponent of matrix multiplication and ${\displaystyle \alpha }$ is the dual exponent of matrix multiplication.[21] ${\displaystyle \alpha }$ is (roughly) defined to be the largest number such that one can multiply an ${\displaystyle n\times n}$ matrix by a ${\displaystyle n\times n^{\alpha }}$ matrix in ${\displaystyle O(n^{2})}$ time. In a followup work by Lee, Song and Zhang, they reproduce the same result via a different method.[22] These two algorithms remain ${\displaystyle {\tilde {O}}(n^{2+1/6}L)}$ when ${\displaystyle \omega =2}$ and ${\displaystyle \alpha =1}$. The result due to Jiang, Song, Weinstein and Zhang improved ${\displaystyle {\tilde {O}}(n^{2+1/6}L)}$ to ${\displaystyle {\tilde {O}}(n^{2+1/18}L)}$.[23]

The current opinion is that the efficiencies of good implementations of simplex-based methods and interior point methods are similar for routine applications of linear programming. However, for specific types of LP problems, it may be that one type of solver is better than another (sometimes much better), and that the structure of the solutions generated by interior point methods versus simplex-based methods are significantly different with the support set of active variables being typically smaller for the latter one.[24]