HOME

TheInfoList



OR:

In
mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
, Dantzig's simplex algorithm (or simplex method) is a popular
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
. The name of the algorithm is derived from the concept of a
simplex In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
and was suggested by T. S. Motzkin. Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial ''
cone A cone is a three-dimensional geometric shape that tapers smoothly from a flat base (frequently, though not necessarily, circular) to a point called the apex or vertex. A cone is formed by a set of line segments, half-lines, or lines con ...
s'', and these become proper simplices with an additional constraint. The simplicial cones in question are the corners (i.e., the neighborhoods of the vertices) of a geometric object called a
polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
. The shape of this polytope is defined by the constraints applied to the objective function.


History

George Dantzig George Bernard Dantzig (; November 8, 1914 – May 13, 2005) was an American mathematical scientist who made contributions to industrial engineering, operations research, computer science, economics, and statistics. Dantzig is known for his ...
worked on planning methods for the US Army Air Force during World War II using a desk calculator. During 1946 his colleague challenged him to mechanize the planning process to distract him from taking another job. Dantzig formulated the problem as linear inequalities inspired by the work of
Wassily Leontief Wassily Wassilyevich Leontief (russian: Васи́лий Васи́льевич Лео́нтьев; August 5, 1905 – February 5, 1999), was a Soviet-American economist known for his research on input–output analysis and how changes in one ec ...
, however, at that time he didn't include an objective as part of his formulation. Without an objective, a vast number of solutions can be feasible, and therefore to find the "best" feasible solution, military-specified "ground rules" must be used that describe how goals can be achieved as opposed to specifying a goal itself. Dantzig's core insight was to realize that most such ground rules can be translated into a linear objective function that needs to be maximized. Development of the simplex method was evolutionary and happened over a period of about a year. After Dantzig included an objective function as part of his formulation during mid-1947, the problem was mathematically more tractable. Dantzig realized that one of the unsolved problems that he had mistaken as homework in his professor
Jerzy Neyman Jerzy Neyman (April 16, 1894 – August 5, 1981; born Jerzy Spława-Neyman; ) was a Polish mathematician and statistician who spent the first part of his professional career at various institutions in Warsaw, Poland and then at University College ...
's class (and actually later solved), was applicable to finding an algorithm for linear programs. This problem involved finding the existence of
Lagrange multipliers In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints (i.e., subject to the condition that one or more equations have to be satisfied e ...
for general linear programs over a continuum of variables, each bounded between zero and one, and satisfying linear constraints expressed in the form of
Lebesgue integral In mathematics, the integral of a non-negative function of a single variable can be regarded, in the simplest case, as the area between the graph of that function and the -axis. The Lebesgue integral, named after French mathematician Henri Lebe ...
s. Dantzig later published his "homework" as a thesis to earn his doctorate. The column geometry used in this thesis gave Dantzig insight that made him believe that the Simplex method would be very efficient.


Overview

The simplex algorithm operates on linear programs in the
canonical form In mathematics and computer science, a canonical, normal, or standard form of a mathematical object is a standard way of presenting that object as a mathematical expression. Often, it is one which provides the simplest representation of an obje ...
:maximize \mathbf \mathbf :subject to A\mathbf \leq \mathbf and \mathbf \ge 0 with \mathbf = (c_1,\, \dots,\, c_n) the coefficients of the objective function, (\cdot)^\mathrm is the
matrix transpose In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations). The tr ...
, and \mathbf = (x_1,\, \dots,\, x_n) are the variables of the problem, A is a ''p''×''n'' matrix, and \mathbf = (b_1,\, \dots,\, b_p). There is a straightforward process to convert any linear program into one in standard form, so using this form of linear programs results in no loss of generality. In geometric terms, the
feasible region In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potent ...
defined by all values of \mathbf such that A\mathbf \le \mathbf and \forall i, x_i \ge 0 is a (possibly unbounded)
convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
. An extreme point or vertex of this polytope is known as '' basic feasible solution'' (BFS). It can be shown that for a linear program in standard form, if the objective function has a maximum value on the feasible region, then it has this value on (at least) one of the extreme points. This in itself reduces the problem to a finite computation since there is a finite number of extreme points, but the number of extreme points is unmanageably large for all but the smallest linear programs. It can also be shown that, if an extreme point is not a maximum point of the objective function, then there is an edge containing the point so that the value of the objective function is strictly increasing on the edge moving away from the point. If the edge is finite, then the edge connects to another extreme point where the objective function has a greater value, otherwise the objective function is unbounded above on the edge and the linear program has no solution. The simplex algorithm applies this insight by walking along edges of the polytope to extreme points with greater and greater objective values. This continues until the maximum value is reached, or an unbounded edge is visited (concluding that the problem has no solution). The algorithm always terminates because the number of vertices in the polytope is finite; moreover since we jump between vertices always in the same direction (that of the objective function), we hope that the number of vertices visited will be small. The solution of a linear program is accomplished in two steps. In the first step, known as Phase I, a starting extreme point is found. Depending on the nature of the program this may be trivial, but in general it can be solved by applying the simplex algorithm to a modified version of the original program. The possible results of Phase I are either that a basic feasible solution is found or that the feasible region is empty. In the latter case the linear program is called ''infeasible''. In the second step, Phase II, the simplex algorithm is applied using the basic feasible solution found in Phase I as a starting point. The possible results from Phase II are either an optimum basic feasible solution or an infinite edge on which the objective function is unbounded above.
George B. Dantzig George Bernard Dantzig (; November 8, 1914 – May 13, 2005) was an American mathematical scientist who made contributions to industrial engineering, operations research, computer science, economics, and statistics. Dantzig is known for his ...
and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.
Robert J. Vanderbei
''Linear Programming: Foundations and Extensions''
3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. .


Standard form

The transformation of a linear program to one in standard form may be accomplished as follows. First, for each variable with a lower bound other than 0, a new variable is introduced representing the difference between the variable and bound. The original variable can then be eliminated by substitution. For example, given the constraint :x_1 \ge 5 a new variable, y_1, is introduced with : \begin y_1 = x_1 - 5\\x_1 = y_1 + 5 \end The second equation may be used to eliminate x_1 from the linear program. In this way, all lower bound constraints may be changed to non-negativity restrictions. Second, for each remaining inequality constraint, a new variable, called a ''
slack variable In an optimization problem, a slack variable is a variable that is added to an inequality constraint to transform it into an equality. Introducing a slack variable replaces an inequality constraint with an equality constraint and a non-negativity co ...
'', is introduced to change the constraint to an equality constraint. This variable represents the difference between the two sides of the inequality and is assumed to be non-negative. For example, the inequalities : \begin x_2 + 2x_3 &\le 3\\ -x_4 + 3x_5 &\ge 2 \end are replaced with : \begin x_2 + 2x_3 + s_1 &= 3\\ -x_4 + 3x_5 - s_2 &= 2\\ s_1,\, s_2 &\ge 0 \end It is much easier to perform algebraic manipulation on inequalities in this form. In inequalities where ≥ appears such as the second one, some authors refer to the variable introduced as a '' surplus variable''. Third, each unrestricted variable is eliminated from the linear program. This can be done in two ways, one is by solving for the variable in one of the equations in which it appears and then eliminating the variable by substitution. The other is to replace the variable with the difference of two restricted variables. For example, if z_1 is unrestricted then write :\begin &z_1 = z_1^+ - z_1^-\\ &z_1^+,\, z_1^- \ge 0 \end The equation may be used to eliminate z_1 from the linear program. When this process is complete the feasible region will be in the form :\mathbf\mathbf = \mathbf,\, \forall i \ x_i \ge 0 It is also useful to assume that the rank of \mathbf is the number of rows. This results in no loss of generality since otherwise either the system \mathbf\mathbf = \mathbf has redundant equations which can be dropped, or the system is inconsistent and the linear program has no solution.


Simplex tableau

A linear program in standard form can be represented as a ''tableau'' of the form : \begin 1 & -\mathbf^T & 0 \\ 0 & \mathbf & \mathbf \end The first row defines the objective function and the remaining rows specify the constraints. The zero in the first column represents the zero vector of the same dimension as vector ''b'' (different authors use different conventions as to the exact layout). If the columns of A can be rearranged so that it contains the
identity matrix In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. Terminology and notation The identity matrix is often denoted by I_n, or simply by I if the size is immaterial o ...
of order ''p'' (the number of rows in A) then the tableau is said to be in ''canonical form''. The variables corresponding to the columns of the identity matrix are called ''basic variables'' while the remaining variables are called ''nonbasic'' or ''free variables''. If the values of the nonbasic variables are set to 0, then the values of the basic variables are easily obtained as entries in ''b'' and this solution is a basic feasible solution. The algebraic interpretation here is that the coefficients of the linear equation represented by each row are either 0, 1, or some other number. Each row will have 1 column with value 1, p-1 columns with coefficients 0, and the remaining columns with some other coefficients (these other variables represent our non-basic variables). By setting the values of the non-basic variables to zero we ensure in each row that the value of the variable represented by a 1 in its column is equal to the b value at that row. Conversely, given a basic feasible solution, the columns corresponding to the nonzero variables can be expanded to a nonsingular matrix. If the corresponding tableau is multiplied by the inverse of this matrix then the result is a tableau in canonical form. Let : \begin 1 & -\mathbf^T_B & -\mathbf^T_D & 0 \\ 0 & I & \mathbf & \mathbf \end be a tableau in canonical form. Additional row-addition transformations can be applied to remove the coefficients from the objective function. This process is called ''pricing out'' and results in a canonical tableau : \begin 1 & 0 & -\bar^T_D & z_B \\ 0 & I & \mathbf & \mathbf \end where ''z''''B'' is the value of the objective function at the corresponding basic feasible solution. The updated coefficients, also known as ''relative cost coefficients'', are the rates of change of the objective function with respect to the nonbasic variables. Evar D. Nering and Albert W. Tucker, 1993, ''Linear Programs and Related Problems'', Academic Press. (elementary)


Pivot operations

The geometrical operation of moving from a basic feasible solution to an adjacent basic feasible solution is implemented as a ''pivot operation''. First, a nonzero ''pivot element'' is selected in a nonbasic column. The row containing this element is multiplied by its reciprocal to change this element to 1, and then multiples of the row are added to the other rows to change the other entries in the column to 0. The result is that, if the pivot element is in a row ''r'', then the column becomes the ''r''-th column of the identity matrix. The variable for this column is now a basic variable, replacing the variable which corresponded to the ''r''-th column of the identity matrix before the operation. In effect, the variable corresponding to the pivot column enters the set of basic variables and is called the ''entering variable'', and the variable being replaced leaves the set of basic variables and is called the ''leaving variable''. The tableau is still in canonical form but with the set of basic variables changed by one element.


Algorithm

Let a linear program be given by a canonical tableau. The simplex algorithm proceeds by performing successive pivot operations each of which give an improved basic feasible solution; the choice of pivot element at each step is largely determined by the requirement that this pivot improves the solution.


Entering variable selection

Since the entering variable will, in general, increase from 0 to a positive number, the value of the objective function will decrease if the derivative of the objective function with respect to this variable is negative. Equivalently, the value of the objective function is increased if the pivot column is selected so that the corresponding entry in the objective row of the tableau is positive. If there is more than one column so that the entry in the objective row is positive then the choice of which one to add to the set of basic variables is somewhat arbitrary and several ''entering variable choice rules'' such as
Devex algorithm In applied mathematics, the devex algorithm is a pivot rule for the simplex method In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is deriv ...
have been developed. If all the entries in the objective row are less than or equal to 0 then no choice of entering variable can be made and the solution is in fact optimal. It is easily seen to be optimal since the objective row now corresponds to an equation of the form :z(\mathbf)=z_B+\text By changing the entering variable choice rule so that it selects a column where the entry in the objective row is negative, the algorithm is changed so that it finds the minimum of the objective function rather than the maximum.


Leaving variable selection

Once the pivot column has been selected, the choice of pivot row is largely determined by the requirement that the resulting solution be feasible. First, only positive entries in the pivot column are considered since this guarantees that the value of the entering variable will be nonnegative. If there are no positive entries in the pivot column then the entering variable can take any non-negative value with the solution remaining feasible. In this case the objective function is unbounded below and there is no minimum. Next, the pivot row must be selected so that all the other basic variables remain positive. A calculation shows that this occurs when the resulting value of the entering variable is at a minimum. In other words, if the pivot column is ''c'', then the pivot row ''r'' is chosen so that :b_r / a_\, is the minimum over all ''r'' so that ''a''''rc'' > 0. This is called the ''minimum ratio test''. If there is more than one row for which the minimum is achieved then a ''dropping variable choice rule'' can be used to make the determination.


Example

Consider the linear program :Minimize ::Z = -2 x - 3 y - 4 z\, :Subject to ::\begin 3 x + 2 y + z &\le 10\\ 2 x + 5 y + 3 z &\le 15\\ x,\,y,\,z &\ge 0 \end With the addition of slack variables ''s'' and ''t'', this is represented by the canonical tableau : \begin 1 & 2 & 3 & 4 & 0 & 0 & 0 \\ 0 & 3 & 2 & 1 & 1 & 0 & 10 \\ 0 & 2 & 5 & 3 & 0 & 1 & 15 \end where columns 5 and 6 represent the basic variables ''s'' and ''t'' and the corresponding basic feasible solution is :x=y=z=0,\,s=10,\,t=15. Columns 2, 3, and 4 can be selected as pivot columns, for this example column 4 is selected. The values of ''z'' resulting from the choice of rows 2 and 3 as pivot rows are 10/1 = 10 and 15/3 = 5 respectively. Of these the minimum is 5, so row 3 must be the pivot row. Performing the pivot produces : \begin 3 & -2 & -11 & 0 & 0 & -4 & -60 \\ 0 & 7 & 1 & 0 & 3 & -1 & 15 \\ 0 & 2 & 5 & 3 & 0 & 1 & 15 \end Now columns 4 and 5 represent the basic variables ''z'' and ''s'' and the corresponding basic feasible solution is :x=y=t=0,\,z=5,\,s=5. For the next step, there are no positive entries in the objective row and in fact :Z = \frac = -20 + \frac so the minimum value of ''Z'' is −20.


Finding an initial canonical tableau

In general, a linear program will not be given in the canonical form and an equivalent canonical tableau must be found before the simplex algorithm can start. This can be accomplished by the introduction of ''artificial variables''. Columns of the identity matrix are added as column vectors for these variables. If the b value for a constraint equation is negative, the equation is negated before adding the identity matrix columns. This does not change the set of feasible solutions or the optimal solution, and it ensures that the slack variables will constitute an initial feasible solution. The new tableau is in canonical form but it is not equivalent to the original problem. So a new objective function, equal to the sum of the artificial variables, is introduced and the simplex algorithm is applied to find the minimum; the modified linear program is called the ''Phase I'' problem. The simplex algorithm applied to the Phase I problem must terminate with a minimum value for the new objective function since, being the sum of nonnegative variables, its value is bounded below by 0. If the minimum is 0 then the artificial variables can be eliminated from the resulting canonical tableau producing a canonical tableau equivalent to the original problem. The simplex algorithm can then be applied to find the solution; this step is called ''Phase II''. If the minimum is positive then there is no feasible solution for the Phase I problem where the artificial variables are all zero. This implies that the feasible region for the original problem is empty, and so the original problem has no solution.


Example

Consider the linear program :Minimize ::Z = -2 x - 3 y - 4 z\, :Subject to ::\begin 3 x + 2 y + z &= 10\\ 2 x + 5 y + 3 z &= 15\\ x,\, y,\, z &\ge 0 \end This is represented by the (non-canonical) tableau : \begin 1 & 2 & 3 & 4 & 0 \\ 0 & 3 & 2 & 1 & 10 \\ 0 & 2 & 5 & 3 & 15 \end Introduce artificial variables ''u'' and ''v'' and objective function ''W'' = ''u'' + ''v'', giving a new tableau : \begin 1 & 0 & 0 & 0 & 0 & -1 & -1 & 0 \\ 0 & 1 & 2 & 3 & 4 & 0 & 0 & 0 \\ 0 & 0 & 3 & 2 & 1 & 1 & 0 & 10 \\ 0 & 0 & 2 & 5 & 3 & 0 & 1 & 15 \end The equation defining the original objective function is retained in anticipation of Phase II. By construction, ''u'' and ''v'' are both basic variables since they are part of the initial identity matrix. However, the objective function ''W'' currently assumes that ''u'' and ''v'' are both 0. In order to adjust the objective function to be the correct value where ''u'' = 10 and ''v'' = 15, add the third and fourth rows to the first row giving : \begin 1 & 0 & 5 & 7 & 4 & 0 & 0 & 25 \\ 0 & 1 & 2 & 3 & 4 & 0 & 0 & 0 \\ 0 & 0 & 3 & 2 & 1 & 1 & 0 & 10 \\ 0 & 0 & 2 & 5 & 3 & 0 & 1 & 15 \end Select column 5 as a pivot column, so the pivot row must be row 4, and the updated tableau is : \begin 3 & 0 & 7 & 1 & 0 & 0 & -4 & 15 \\ 0 & 3 & -2 & -11 & 0 & 0 & -4 & -60 \\ 0 & 0 & 7 & 1 & 0 & 3 & -1 & 15 \\ 0 & 0 & 2 & 5 & 3 & 0 & 1 & 15 \end Now select column 3 as a pivot column, for which row 3 must be the pivot row, to get : \begin 7 & 0 & 0 & 0 & 0 & -7 & -7 & 0 \\ 0 & 7 & 0 & -25 & 0 & 2 & -10 & -130 \\ 0 & 0 & 7 & 1 & 0 & 3 & -1 & 15 \\ 0 & 0 & 0 & 11 & 7 & -2 & 3 & 25 \end The artificial variables are now 0 and they may be dropped giving a canonical tableau equivalent to the original problem: : \begin 7 & 0 & -25 & 0 & -130 \\ 0 & 7 & 1 & 0 & 15 \\ 0 & 0 & 11 & 7 & 25 \end This is, fortuitously, already optimal and the optimum value for the original linear program is −130/7.


Advanced topics


Implementation

The tableau form used above to describe the algorithm lends itself to an immediate implementation in which the tableau is maintained as a rectangular (''m'' + 1)-by-(''m'' + ''n'' + 1) array. It is straightforward to avoid storing the m explicit columns of the identity matrix that will occur within the tableau by virtue of B being a subset of the columns of ''A, I This implementation is referred to as the "''standard'' simplex algorithm". The storage and computation overhead is such that the standard simplex method is a prohibitively expensive approach to solving large linear programming problems. In each simplex iteration, the only data required are the first row of the tableau, the (pivotal) column of the tableau corresponding to the entering variable and the right-hand-side. The latter can be updated using the pivotal column and the first row of the tableau can be updated using the (pivotal) row corresponding to the leaving variable. Both the pivotal column and pivotal row may be computed directly using the solutions of linear systems of equations involving the matrix B and a matrix-vector product using A. These observations motivate the " ''revised'' simplex algorithm", for which implementations are distinguished by their invertible representation of B.
George B. Dantzig George Bernard Dantzig (; November 8, 1914 – May 13, 2005) was an American mathematical scientist who made contributions to industrial engineering, operations research, computer science, economics, and statistics. Dantzig is known for his ...
and Mukund N. Thapa. 2003. ''Linear Programming 2: Theory and Extensions''. Springer-Verlag.
In large linear-programming problems A is typically a
sparse matrix In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse b ...
and, when the resulting sparsity of B is exploited when maintaining its invertible representation, the revised simplex algorithm is much more efficient than the standard simplex method. Commercial simplex solvers are based on the revised simplex algorithm.M. Padberg, ''Linear Optimization and Extensions'', Second Edition, Springer-Verlag, 1999.


Degeneracy: stalling and cycling

If the values of all basic variables are strictly positive, then a pivot must result in an improvement in the objective value. When this is always the case no set of basic variables occurs twice and the simplex algorithm must terminate after a finite number of steps. Basic feasible solutions where at least one of the ''basic ''variables is zero are called ''degenerate'' and may result in pivots for which there is no improvement in the objective value. In this case there is no actual change in the solution but only a change in the set of basic variables. When several such pivots occur in succession, there is no improvement; in large industrial applications, degeneracy is common and such "''stalling''" is notable. Worse than stalling is the possibility the same set of basic variables occurs twice, in which case, the deterministic pivoting rules of the simplex algorithm will produce an infinite loop, or "cycle". While degeneracy is the rule in practice and stalling is common, cycling is rare in practice. A discussion of an example of practical cycling occurs in Padberg.
Bland's rule In mathematical optimization, Bland's rule (also known as Bland's algorithm, Bland's anti-cycling rule or Bland's pivot rule) is an algorithmic refinement of the simplex method for linear optimization. With Bland's rule, the simplex algorithm solve ...
prevents cycling and thus guarantees that the simplex algorithm always terminates. Another pivoting algorithm, the
criss-cross algorithm In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear object ...
never cycles on linear programs. History-based pivot rules such as Zadeh's rule and Cunningham's rule also try to circumvent the issue of stalling and cycling by keeping track of how often particular variables are being used and then favor such variables that have been used least often.


Efficiency in the worst case

The simplex method is remarkably efficient in practice and was a great improvement over earlier methods such as
Fourier–Motzkin elimination Fourier–Motzkin elimination, also known as the FME method, is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can output real solutions. The algorithm is named after Joseph Fourier who proposed the me ...
. However, in 1972,
Klee Paul Klee (; 18 December 1879 – 29 June 1940) was a Swiss-born German artist. His highly individual style was influenced by movements in art that included expressionism, cubism, and surrealism. Klee was a natural draftsman who experimented wi ...
and Minty gave an example, the
Klee–Minty cube The Klee–Minty cube or Klee–Minty polytope (named after Victor Klee and George J. Minty) is a unit cube, unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorith ...
, showing that the worst-case complexity of simplex method as formulated by Dantzig is
exponential time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
. Since then, for almost every variation on the method, it has been shown that there is a family of linear programs for which it performs badly. It is an open question if there is a variation with
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
, although sub-exponential pivot rules are known. In 2014, it was proved that a particular variant of the simplex method is NP-mighty, i.e., it can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm's execution. Moreover, deciding whether a given variable ever enters the basis during the algorithm's execution on a given input, and determining the number of iterations needed for solving a given problem, are both
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
problems. At about the same time it was shown that there exists an artificial pivot rule for which computing its output is
PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can b ...
. In 2015, this was strengthened to show that computing the output of Dantzig's pivot rule is
PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can b ...
.


Efficiency in practice

Analyzing and quantifying the observation that the simplex algorithm is efficient in practice despite its exponential worst-case complexity has led to the development of other measures of complexity. The simplex algorithm has polynomial-time average-case complexity under various
probability distribution In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
s, with the precise average-case performance of the simplex algorithm depending on the choice of a probability distribution for the
random matrices In probability theory and mathematical physics, a random matrix is a matrix-valued random variable—that is, a matrix in which some or all elements are random variables. Many important properties of physical systems can be represented mathemat ...
.
Alexander Schrijver Alexander (Lex) Schrijver (born 4 May 1948 in Amsterdam) is a Dutch mathematician and computer scientist, a professor of discrete mathematics and optimization at the University of Amsterdam and a fellow at the Centrum Wiskunde & Informatica in ...
, ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, (mathematical)
The simplex algorithm takes on average ''D'' steps for a cube. : Another approach to studying " typical phenomena" uses Baire category theory from
general topology In mathematics, general topology is the branch of topology that deals with the basic set-theoretic definitions and constructions used in topology. It is the foundation of most other branches of topology, including differential topology, geomet ...
, and to show that (topologically) "most" matrices can be solved by the simplex algorithm in a polynomial number of steps. Another method to analyze the performance of the simplex algorithm studies the behavior of worst-case scenarios under small perturbation – are worst-case scenarios stable under a small change (in the sense of structural stability), or do they become tractable? This area of research, called
smoothed analysis In theoretical computer science, smoothed analysis is a way of measuring the complexity of an algorithm. Since its introduction in 2001, smoothed analysis has been used as a basis for considerable research, for problems ranging from mathematical ...
, was introduced specifically to study the simplex method. Indeed, the running time of the simplex method on input with noise is polynomial in the number of variables and the magnitude of the perturbations.


Other algorithms

Other algorithms for solving linear-programming problems are described in the linear-programming article. Another basis-exchange pivoting algorithm is the
criss-cross algorithm In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear object ...
. There are polynomial-time algorithms for linear programming that use interior point methods: these include
Khachiyan Leonid Genrikhovich Khachiyan (; russian: Леони́д Ге́нрихович Хачия́н; May 3, 1952April 29, 2005) was a Soviet and American mathematician and computer scientist. He was most famous for his ellipsoid algorithm (1979) fo ...
's ellipsoidal algorithm,
Karmarkar Narendra Krishna Karmarkar (born Circa 1956) is an Indian Mathematician. Karmarkar developed Karmarkar's algorithm. He is listed as an ISI highly cited researcher. He invented one of the first provably polynomial time algorithms for linear pro ...
's projective algorithm, and path-following algorithms.


Linear-fractional programming

Linear–fractional programming (LFP) is a generalization of
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
(LP). In LP the objective function is a
linear function In mathematics, the term linear function refers to two distinct but related notions: * In calculus and related areas, a linear function is a function (mathematics), function whose graph of a function, graph is a straight line, that is, a polynomia ...
, while the objective function of a linear–fractional program is a ratio of two linear functions. In other words, a linear program is a fractional–linear program in which the denominator is the constant function having the value one everywhere. A linear–fractional program can be solved by a variant of the simplex algorithm or by the
criss-cross algorithm In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear object ...
.


See also

*
Criss-cross algorithm In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear object ...
*
Cutting-plane method In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed ''cuts''. Such procedures are commonly used ...
*
Devex algorithm In applied mathematics, the devex algorithm is a pivot rule for the simplex method In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is deriv ...
*
Fourier–Motzkin elimination Fourier–Motzkin elimination, also known as the FME method, is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can output real solutions. The algorithm is named after Joseph Fourier who proposed the me ...
*
Gradient descent In mathematics, gradient descent (also often called steepest descent) is a first-order iterative optimization algorithm for finding a local minimum of a differentiable function. The idea is to take repeated steps in the opposite direction of the ...
*
Karmarkar's algorithm Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also pol ...
* Nelder–Mead simplicial heuristic * Pivoting rule of Bland, which avoids cycling


Notes


References

*


Further reading

These introductions are written for students of
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
and
operations research Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...
: *
Thomas H. Cormen Thomas H. Cormen is the co-author of ''Introduction to Algorithms'', along with Charles Leiserson, Ron Rivest, and Cliff Stein. In 2013, he published a new book titled '' Algorithms Unlocked''. He is a professor of computer science at Dartmout ...
,
Charles E. Leiserson Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. ...
,
Ronald L. Rivest Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Inte ...
, and
Clifford Stein Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Scien ...
. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. . Section 29.3: The simplex algorithm, pp. 790–804. * Frederick S. Hillier and Gerald J. Lieberman: ''Introduction to Operations Research'', 8th edition. McGraw-Hill. *


External links


An Introduction to Linear Programming and the Simplex Algorithm
by Spyros Reveliotis of the Georgia Institute of Technology. *Greenberg, Harvey J., ''Klee–Minty Polytope Shows Exponential Time Complexity of Simplex Method'' the University of Colorado at Denver (1997
PDF downloadSimplex Method
A tutorial for Simplex Method with examples (also two-phase and M-method).
Mathstools
Simplex Calculator from www.mathstools.com

by Thomas McFarland of the University of Wisconsin-Whitewater.

by Daniel Izquierdo and Juan José Ruiz of the University of Málaga (UMA, Spain)
simplex-m
Online Simplex Solver {{DEFAULTSORT:Simplex Algorithm Optimization algorithms and methods 1947 in computing Exchange algorithms Linear programming Computer-related introductions in 1947