Linear programming is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given
mathematical modelA mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used not only in the natural sciences and engineering disciplines A mathematical model is a...
for some list of requirements represented as linear relationships. Linear programming is a specific case of mathematical programming (mathematical optimization).
More formally, linear programming is a technique for the optimization of a
linearIn mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...
objective function, subject to linear equality and
linear inequalityIn mathematics a linear inequality is an inequality which involves a linear function.Definitions:When two expressions are connected by 'greater than' or 'less than' sign, we get an inequation....
constraintsIn mathematics, a constraint is a condition that a solution to an optimization problem must satisfy. There are two types of constraints: equality constraints and inequality constraints...
. Its feasible region is a convex polyhedron, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a
realIn mathematics, a real number is a value that represents a quantity along a continuum, such as 5 , 4/3 , 8.6 , √2 and π...
valued affine function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such point exists.
Linear programs are problems that can be expressed in
canonical formGenerally, in mathematics, a canonical form of an object is a standard way of presenting that object....
:
where x represents the vector of variables (to be determined), c and b are
vectorsA vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
of (known) coefficients and A is a (known)
matrixIn mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
of coefficients. The expression to be maximized or minimized is called the objective function (c
^{T}x in this case). The equations Ax ≤ b are the constraints which specify a
convex polytopeA convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the ndimensional space Rn...
over which the objective function is to be optimized. (In this context, two vectors are
comparableIn mathematics, any two elements x and y of a set P that is partially ordered by a binary relation ≤ are comparable when either x ≤ y or y ≤ x...
when every entry in one is lessthan or equalto the corresponding entry in the other. Otherwise, they are incomparable.)
Linear programming can be applied to various fields of study. It is used most extensively in business and economics, but can also be utilized for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proved useful in modeling diverse types of problems in planning, routing, scheduling,
assignmentThe assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics...
, and design.
History
The problem of solving a system of linear inequalities dates back at least as far as
FourierJean Baptiste Joseph Fourier was a French mathematician and physicist best known for initiating the investigation of Fourier series and their applications to problems of heat transfer and vibrations. The Fourier transform and Fourier's Law are also named in his honour...
, after whom the method of FourierMotzkin elimination is named. The three founders of the subject are considered to be
Leonid KantorovichLeonid Vitaliyevich Kantorovich was a Soviet mathematician and economist, known for his theory and development of techniques for the optimal allocation of resources...
, the Russian mathematician who developed the earliest linear programming problems in 1939,
George DantzigGeorge Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....
, who published the
simplex methodIn mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
in 1947, and
John von NeumannJohn von Neumann was a HungarianAmerican mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
, who developed the theory of the duality in the same year. The earliest linear programming was first developed by
Leonid KantorovichLeonid Vitaliyevich Kantorovich was a Soviet mathematician and economist, known for his theory and development of techniques for the optimal allocation of resources...
, a Russian mathematician, in 1939. It was used during
World War IIWorld War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
to plan expenditures and returns in order to reduce costs to the army and increase losses to the enemy. The method was kept secret until 1947 when
George B. DantzigGeorge Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....
published the
simplex methodIn mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
and
John von NeumannJohn von Neumann was a HungarianAmerican mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
developed the theory of duality as a linear optimization solution, and applied it in the field of
game theoryGame theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
. Postwar, many industries found its use in their daily planning.
The linearprogramming problem was first shown to be solvable in polynomial time by
Leonid KhachiyanLeonid Genrikhovich Khachiyan was a Soviet mathematician of Armenian descent who taught Computer Science at Rutgers University. He was most famous for his Ellipsoid algorithm for linear programming, which was the first such algorithm known to have a polynomial running time...
in 1979, but a larger theoretical and practical breakthrough in the field came in 1984 when
Narendra KarmarkarNarendra K. Karmarkar is an Indian mathematician, renowned for developing Karmarkar's algorithm. He is listed as an ISI highly cited researcher. Biography :...
introduced a new interiorpoint method for solving linearprogramming problems.
Dantzig's original example of finding the best assignment of 70 people to 70 jobs exemplifies the usefulness of linear programming. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the Simplex algorithm. The theory behind linear programming drastically reduces the number of possible optimal solutions that must be checked.
Uses
Linear programming is a considerable field of optimization for several reasons. Many practical problems in
operations researchOperations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as subproblems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. Likewise, linear programming is heavily used in
microeconomicsMicroeconomics is a branch of economics that studies the behavior of how the individual modern household and firms make decisions to allocate limited resources. Typically, it applies to markets where goods or services are being bought and sold...
and company management, such as planning, production, transportation, technology and other issues. Although the modern management issues are everchanging, most companies would like to maximize profits or minimize costs with limited resources. Therefore, many issues can be characterized as linear programming problems.
Standard form
Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following four parts:
 A linear function to be maximized
 e.g.
 Problem constraints of the following form
 e.g.

 e.g.

 Nonnegative right hand side constants


The problem is usually expressed in matrixIn mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
form, and then becomes:

Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variableIn computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...
s can always be rewritten into an equivalent problem in standard form.
Example
Suppose that a farmer has a piece of farm land, say L km^{2}, 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 insecticide, P kilograms. Every square kilometer of wheat requires F_{1} kilograms of fertilizer, and P_{1} kilograms of insecticide, while every square kilometer of barley requires F_{2} kilograms of fertilizer, and P_{2} kilograms of insecticide. Let S_{1} be the selling price of wheat per square kilometer, and S_{2} be the price of barley. If we denote the area of land planted with wheat and barley by x_{1} and x_{2} respectively, then profit can be maximized by choosing optimal values for x_{1} and x_{2}. This problem can be expressed with the following linear programming problem in the standard form:
Maximize: S_{1}x_{1} + S_{2}x_{2} 
(maximize the revenue—revenue is the "objective function") 
Subject to: 
0 ≤ x_{1} + x_{2} ≤ L 
(limit on total area) 

0 ≤ F_{1}x_{1} + F_{2}x_{2} ≤ F 
(limit on fertilizer) 

0 ≤ P_{1}x_{1} + P_{2}x_{2} ≤ P 
(limit on insecticide) 

x_{1} ≥ 0, x_{2} ≥ 0 
(cannot plant a negative area). 
Which in matrix form becomes:
 maximize
 subject to
Augmented form (slack form)
Linear programming problems must be converted into augmented form before being solved by the simplex algorithmIn mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
. This form introduces nonnegative slack variableIn an optimization problem, a slack variable is a variable that is added to an inequality constraint to transform it to an equality. Introducing a slack variable replaces an inequality constraint with an equality constraint and a nonnegativity constraint....
s to replace inequalities with equalities in the constraints. The problem can then be written in the following block matrixIn the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a matrix broken into sections called blocks. Looking at it another way, the matrix is written in terms of smaller matrices. We group the rows and columns into adjacent 'bunches'. A partition is the rectangle...
form:
 Maximize Z:

 x, x_{s} ≥ 0
where x_{s} are the newly introduced slack variables, and Z is the variable to be maximized.
Example
The example above is converted into the following augmented form:
Maximize: S_{1}x_{1} + S_{2}x_{2} 
(objective function) 
Subject to: 
x_{1} + x_{2} + x_{3} = L 
(augmented constraint) 

F_{1}x_{1} + F_{2}x_{2} + x_{4} = F 
(augmented constraint) 

P_{1}x_{1} + P_{2}x_{2} + x_{5} = P 
(augmented constraint) 

x_{1}, x_{2}, x_{3}, x_{4}, x_{5} ≥ 0. 
where x_{3}, x_{4}, x_{5} are (nonnegative) slack variables, representing in this example the unused area, the amount of unused fertilizer, and the amount of unused insecticide.
In matrix form this becomes:
 Maximize Z:

Duality
Every linear programming problem, referred to as a primal problem, can be converted into a dual problemIn constrained optimization, it is often possible to convert the primal problem to a dual form, which is termed a dual problem. Usually dual problem refers to the Lagrangian dual problem but other dual problems are used, for example, the Wolfe dual problem and the Fenchel dual problem...
, which provides an upper bound to the optimal value of the primal problem. In matrix form, we can express the primal problem as:
 Maximize c^{T}x subject to Ax ≤ b, x ≥ 0;
 with the corresponding symmetric dual problem,
 Minimize b^{T}y subject to A^{T}y ≥ c, y ≥ 0.
An alternative primal formulation is:
 Maximize c^{T}x subject to Ax ≤ b;
 with the corresponding asymmetric dual problem,
 Minimize b^{T}y subject to A^{T}y = c, y ≥ 0.
There are two ideas fundamental to duality theory. One is the fact that (for the symmetric dual) the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual. The weak duality theorem states that the objective function value of the dual at any feasible solution is always greater than or equal to the objective function value of the primal at any feasible solution. The strong duality theorem states that if the primal has an optimal solution, x^{*}, then the dual also has an optimal solution, y^{*}, such that c^{T}x^{*}=b^{T}y^{*}.
A linear program can also be unbounded or infeasible. Duality theory tells us that if the primal is unbounded then the dual is infeasible by the weak duality theorem. Likewise, if the dual is unbounded, then the primal must be infeasible. However, it is possible for both the dual and the primal to be infeasible (See also Farkas' lemma).
Example
Revisit the above example of the farmer who may grow wheat and barley with the set provision of some L land, F fertilizer and P insecticide. Assume now that unit prices for each of these means of production (inputs) are set by a planning board. The planning board's job is to minimize the total cost of procuring the set amounts of inputs while providing the farmer with a floor on the unit price of each of his crops (outputs), S_{1} for wheat and S_{2} for barley. This corresponds to the following linear programming problem:
Minimize: Ly_{L} + Fy_{F} + Py_{P} 
(minimize the total cost of the means of production as the "objective function") 
Subject to: 
y_{L} + F_{1}y_{F} + P_{1}y_{P} ≥ S_{1} 
(the farmer must receive no less than S_{1} for his wheat) 

y_{L} + F_{2} y_{F} + P_{2}y_{P} ≥ S_{2} 
(the farmer must receive no less than S_{2} for his barley) 

y_{L} ≥ 0, y_{F} ≥ 0, y_{P} ≥ 0 
(prices cannot be negative). 
Which in matrix form becomes:
 Minimize:
 Subject to:
The primal problem deals with physical quantities. With all inputs available in limited quantities, and assuming the unit prices of all outputs is known, what quantities of outputs to produce so as to maximize total revenue? The dual problem deals with economic values. With floor guarantees on all output unit prices, and assuming the available quantity of all inputs is known, what input unit pricing scheme to set so as to minimize total expenditure?
To each variable in the primal space corresponds an inequality to satisfy in the dual space, both indexed by output type. To each inequality to satisfy in the primal space corresponds a variable in the dual space, both indexed by input type.
The coefficients that bound the inequalities in the primal space are used to compute the objective in the dual space, input quantities in this example. The coefficients used to compute the objective in the primal space bound the inequalities in the dual space, output unit prices in this example.
Both the primal and the dual problems make use of the same matrix. In the primal space, this matrix expresses the consumption of physical quantities of inputs necessary to produce set quantities of outputs. In the dual space, it expresses the creation of the economic values associated with the outputs from set input unit prices.
Since each inequality can be replaced by an equality and a slack variable, this means each primal variable corresponds to a dual slack variable, and each dual variable corresponds to a primal slack variable. This relation allows us to complementary slackness.
Another example
Sometimes, one may find it more intuitive to obtain the dual program without looking at program matrix. Consider the following linear program:
minimize 

subject to 

, 



, 



, 

We have m + n conditions and all variables are nonnegative. We shall define m + n dual variables: y_{j} and s_{i}. We get:
minimize 

subject to 

, 



, 



, 



, 

Since this is a minimization problem, we would like to obtain a dual program that is a lower bound of the primal. In other words, we would like the sum of all right hand side of the constraints to be the maximal under the condition that for each primal variable the sum of its coefficientIn mathematics, a coefficient is a multiplicative factor in some term of an expression ; it is usually a number, but in any case does not involve any variables of the expression...
s do not exceed its coefficient in the linear function. For example, x_{1} appears in n + 1 constraints. If we sum its constraints' coefficients we get a_{1,1}y_{1} + a_{1,2}y_{2} + ... + a_{1,n}y_{n} + f_{1}s_{1}. This sum must be at most c_{1}. As a result we get:
maximize 

subject to 

, 



, 



, 

Note that we assume in our calculations steps that the program is in standard form. However, any linear program may be transformed to standard form and it is therefore not a limiting factor.
Coveringpacking dualities
A covering LPIn combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that....
is a linear program of the form:
 Minimize: b^{T}y,
 Subject to: A^{T}y ≥ c, y ≥ 0,
such that the matrix A and the vectors b and c are nonnegative.
The dual of a covering LP is a packing LPPacking problems are a class of optimization problems in mathematics which involve attempting to pack objects together , as densely as possible. Many of these problems can be related to real life packaging, storage and transportation issues...
, a linear program of the form:
 Maximize: c^{T}x,
 Subject to: Ax ≤ b, x ≥ 0,
such that the matrix A and the vectors b and c are nonnegative.
Examples
Covering and packing LPs commonly arise as a linear programming relaxation of a combinatorial problem and are important in the study of approximation algorithms. For example, the LP relaxations of the set packing problemSet packing is a classical NPcomplete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NPcomplete problems.Suppose we have a finite set S and a list of subsets of S...
, the independent set problem, and the matching problem are packing LPs. The LP relaxations of the set cover problemThe set covering problem is a classical question in computer science and complexity theory.It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms...
, the vertex cover problem, and the dominating set problem are also covering LPs.
Finding a fractional coloringFractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent vertices — those connected by edges — must be assigned...
of a graphIn mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
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 setIn graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
of the graph.
Complementary slackness
It is possible to obtain an optimal solution to the dual when only an optimal solution to the primal is known using the complementary slackness theorem. The theorem states:
Suppose that x = (x_{1}, x_{2}, ... , x_{n}) is primal feasible and that y = (y_{1}, y_{2}, ... , y_{m}) is dual feasible. Let (w_{1}, w_{2}, ..., w_{m}) denote the corresponding primal slack variables, and let (z_{1}, z_{2}, ... , z_{n}) denote the corresponding dual slack variables. Then x and y are optimal for their respective problems if and only if
 x_{j}z_{j} = 0, for j = 1, 2, ... , n, and
 w_{i}y_{i} = 0, for i = 1, 2, ... , m.
So if the ith slack variable of the primal is not zero, then the ith variable of the dual is equal zero. Likewise, if the jth slack variable of the dual is not zero, then the jth variable of the primal is equal to zero.
This necessary condition for optimality conveys a fairly simple economic principle. In standard form (when maximizing), if there is slack in a constrained primal resource (i.e., there are "leftovers"), then additional quantities of that resource must have no value. Likewise, if there is slack in the dual (shadow) price nonnegativity constraint requirement, i.e., the price is not zero, then there must be scarce supplies (no "leftovers").
Existence of optimal solutions
Geometrically, the linear constraints define the feasible region, which is a convexIn Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
polyhedronIn elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
. A linear functionIn linear algebra, a linear functional or linear form is a linear map from a vector space to its field of scalars. In Rn, if vectors are represented as column vectors, then linear functionals are represented as row vectors, and their action on vectors is given by the dot product, or the...
is a convex functionIn mathematics, a realvalued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...
, which implies that every local minimum is a global minimum; similarly, a linear function is a concave functionIn mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.Definition:...
, which implies that every local maximum is a global maximum.
Optimal solution need not exist, for two reasons. First, if two 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 polytopeIn elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
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.
Optimal vertices (and rays) of polyhedra
Otherwise, if a feasible solution exists and if the (linear) objective function is bounded, then the optimum value is always attained on the boundary of optimal levelset, by the maximum principleIn mathematics, the maximum principle is a property of solutions to certain partial differential equations, of the elliptic and parabolic types. Roughly speaking, it says that the maximum of a function in a domain is to be found on the boundary of that domain...
for convex functionIn mathematics, a realvalued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...
s (alternatively, by the minimum principle for concave functionIn mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.Definition:...
s): Recall that 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 zerofunction for its objectivefunction, 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 algorithmSimplex algorithmIn mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century.... for solving linear programs.
Algorithms
Simplex algorithm of Dantzig
The simplex algorithmSimplex algorithmIn mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century...., developed by George DantzigGeorge DantzigGeorge Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics.... 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 nondecreasing values of the objective function until an optimum is reached. In many practical problems, "stalling" occurs: Many pivots are made with no increase in the objective function. In rare practical problems, the usual versions of the simplex algorithm may actually "cycle". To avoid cycles, researchers developed new pivoting rules .
In practice, the simplex algorithmAlgorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of welldefined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning... 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, which is similar to its behavior on practical problems.
However, the simplex algorithm has poor worstcase 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. In fact, for some time it was not known whether the linear programming problem was solvable in polynomial time, i.e. of complexity class PP (complexity)In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds....
Crisscross algorithm
Like the simplex algorithm of Dantzig, the crisscross algorithmCrisscross algorithmIn mathematical optimization, the crisscross algorithm denotes a family of algorithms for linear programming. Variants of the crisscross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are crisscross algorithms for... is a basisexchange algorithm that pivots between bases. However, the crisscross algorithm need not maintain feasibility, but can pivot rather from a feasible basis to an infeasible basis. The crisscross algorithm does not have polynomial timecomplexityTime complexityIn computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and... for linear programming. Both algorithms visit all 2D corners of a (perturbed) cubeUnit cubeA unit cube, sometimes called a cube of side 1, is a cube whose sides are 1 unit long. The volume of a 3dimensional unit cube is 1 cubic unit, and its total surface area is 6 square units. Unit Hypercube :... in dimension D, the Klee–Minty cubeKlee–Minty cubeThe Klee–Minty cube is a unit cube whose corners have been slightly perturbed. Klee and Minty demonstrated that Dantzig's simplex algorithm has poor worstcase performance when initialized at one corner of their "squashed cube".In particular, many optimization algorithms for linear optimization... (after Victor KleeVictor KleeVictor L. Klee, Jr. was a mathematician specialising in convex sets, functional analysis, analysis of algorithms, optimization, and combinatorics. He spent almost his entire career at the University of Washington in Seattle.Born in San Francisco, Vic Klee earned his B.A... and George J. Minty), in the worst case.
Ellipsoid algorithm, following Khachiyan
This is the first worstcase polynomialtime algorithm for linear programming. To solve a problem which has n variables and can be encoded in L input bits, this algorithm uses O(n4L) pseudoarithmetic operations on numbers with O(L) digits. Khachiyan's algorithmAlgorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of welldefined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning... and his long standing issue was resolved by Leonid KhachiyanLeonid KhachiyanLeonid Genrikhovich Khachiyan was a Soviet mathematician of Armenian descent who taught Computer Science at Rutgers University. He was most famous for his Ellipsoid algorithm for linear programming, which was the first such algorithm known to have a polynomial running time... in 1979 with the introduction of the ellipsoid methodEllipsoid methodIn mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm, which finds an optimal solution in a finite number of steps.The.... The convergence analysis have (realnumber) predecessors, notably the iterative methodIterative methodIn computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...s developed by Naum Z. ShorNaum Z. ShorNaum Zuselevich Shor was a Soviet and Ukrainian Jewish mathematician specializing in optimization.He made significant contributions to nonlinear and stochastic programming, numerical techniques for nonsmooth optimization, discrete optimization problems, matrix optimization, dual quadratic bounds... and the approximation algorithmApproximation algorithmIn computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NPhard problems; since it is unlikely that there can ever be efficient polynomial time exact...s by Arkadi Nemirovski and D. Yudin.
Projective algorithm of Karmarkar
Khachiyan's algorithm was of landmark importance for establishing the polynomialtime solvability of linear programs. The algorithm was not a computational breakthrough, 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. KarmarkarNarendra KarmarkarNarendra K. Karmarkar is an Indian mathematician, renowned for developing Karmarkar's algorithm. He is listed as an ISI highly cited researcher. Biography :... proposed a projective method for linear programming. Karmarkar's algorithmKarmarkar's algorithmKarmarkar'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... improved on Khachiyan's worstcase polynomial bound (giving ). Karmarkar claimed that his algorithm was much faster in practical LP than the simplex method, a claim that created great interest in interiorpoint methods. Its projective geometry is interesting.
Pathfollowing algorithms
In contrast to the simplex algorithm, which finds an optimal solution by traversing the edges between vertices on a polyhedral set, interiorpoint methods move through the interior of the feasible region. Since then, many interiorpoint methods have been proposed and analyzed. Early successful implementations were based on affine scaling variants of the method. For both theoretical and practical purposes, barrier functionBarrier functionIn constrained optimization, a field of mathematics, a barrier function is a continuous function whose value on a point increases to infinity as the point approaches the boundary of the feasible region . It is used as a penalizing term for violations of constraints... or pathfollowing methods have been the most popular since the 1990s.
Comparison of interiorpoint methods versus simplex algorithms
The current opinion is that the efficiency of good implementations of simplexbased 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).
LP solvers are in widespread use for optimization of various problems in industry, such as optimization of flow in transportation networks.
Open problems and recent work
There are several open problems in the theory of linear programming, the solution of which would represent fundamental breakthroughs in mathematics and potentially major advances in our ability to solve largescale linear programs.
Does LP admit a strongly polynomialtime algorithm?
Does LP admit a strongly polynomial algorithm to find a strictly complementary solution?
Does LP admit a polynomial algorithm in the real number (unit cost) model of computation?
This closely related set of problems has been cited by Stephen SmaleStephen SmaleSteven Smale a.k.a. Steve Smale, Stephen Smale is an American mathematician from Flint, Michigan. He was awarded the Fields Medal in 1966, and spent more than three decades on the mathematics faculty of the University of California, Berkeley .Education and career:He entered the University of... as among the 18 greatest unsolved problemsSmale's problemsSmale's problems refers to a list of eighteen unsolved problems in mathematics that was proposed by Steve Smale in 2000. Smale composed this list in reply to a request from Vladimir Arnold, then president of the International Mathematical Union, who asked several mathematicians to propose a list of... of the 21st century. In Smale's words, the third version of the problem "is the main unsolved problem of linear programming theory." While algorithms exist to solve linear programming in weakly polynomial time, such as the ellipsoid methodEllipsoid methodIn mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm, which finds an optimal solution in a finite number of steps.The...s and interiorpoint techniquesInterior point methodInterior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems.The interior point method was invented by John von Neumann..., no algorithms have yet been found that allow strongly polynomialtime performance in the number of constraints and the number of variables. The development of such algorithms would be of great theoretical interest, and perhaps allow practical gains in solving large LPs as well.
Although the Hirsch conjectureHirsch conjectureIn mathematical programming and polyhedral combinatorics, Hirsch's conjecture states that the edgevertex graph of an nfacet polytope in ddimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a... was recently disproved for higher dimensions, it still leaves the following questions open.
Are there pivot rules which lead to polynomialtime Simplex variants?
Do all polytopal graphs have polynomiallybounded diameter?
These questions relate to the performance analysis and development of Simplexlike methods. The immense efficiency of the Simplex algorithm in practice despite its exponentialtime theoretical performance hints that there may be variations of Simplex that run in polynomial or even strongly polynomial time. It would be of great practical and theoretical significance to know whether any such variants exist, particularly as an approach to deciding if LP can be solved in strongly polynomial time.
The Simplex algorithm and its variants fall in the family of edgefollowing algorithms, so named because they solve linear programming problems by moving from vertex to vertex along edges of a polytope. This means that their theoretical performance is limited by the maximum number of edges between any two vertices on the LP polytope. As a result, we are interested in knowing the maximum graphtheoretical diameter of polytopal graphsGraph (mathematics)In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.... It has been proved that all polytopes have subexponential diameter. The recent disproof of the Hirsch conjecture is the first step to prove whether any polytope has superpolynomial diameter. If any such polytopes exist, then no edgefollowing variant can run in polynomial time. Questions about polytope diameter are of independent mathematical interest.
Simplex pivot methods preserve primal (or dual) feasibility. On the other hand, crisscross pivot methods do not preserve (primal or dual) feasibility—they may visit primal feasible, dual feasible or primalanddual infeasible bases in any order. Pivot methods of this type have been studied since the 1970s. Essentially, these methods attempt to find the shortest pivot path on the arrangement polytope under the linear programming problem. In contrast to polytopal graphs, graphs of arrangement polytopes are known to have small diameter, allowing the possibility of strongly polynomialtime crisscross pivot algorithm without resolving questions about the diameter of general polytopes.
Integer unknowns
If the unknown variables are all required to be integers, then the problem is called an integer programmingInteger programmingAn integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NPhard... (IP) or integer linear programming (ILP) problem. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) NPhardNPhardNPhard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NPhard if and only if there is an NPcomplete problem L that is polynomial time Turingreducible to H.... 01 integer programming or binary integer programming (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NPhard, and in fact the decision version was one of Karp's 21 NPcomplete problemsKarp's 21 NPcomplete problemsOne of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NPcomplete problem, the boolean satisfiability problem....
If only some of the unknown variables are required to be integers, then the problem is called a mixed integer programming (MIP) problem. These are generally also NPhard.
There are however some important subclasses of IP and MIP problems that are efficiently solvable, most notably problems where the constraint matrix is totally unimodular and the righthand sides of the constraints are integers.
Advanced algorithms for solving integer linear programs include:
cuttingplane methodCuttingplane methodIn mathematical optimization, the cuttingplane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts...
branch and boundBranch and boundBranch and bound is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization...
branch and cutBranch and cutBranch and cut is a method of combinatorial optimization for solving integer linear programs, that is, linear programming problems where some or all the unknowns are restricted to integer values...
branch and priceBranch and priceIn applied mathematics, branch and price is a method of combinatorial optimization for solving integer linear programs,...
if the problem has some extra structure, it may be possible to apply delayed column generationDelayed column generationDelayed column generation is an efficient algorithm for solving larger linear programs.The overarching idea is that many linear programs are too large to consider all the variables explicitly. Since most of the variables will be nonbasic and assume a value of zero in the optimal solution, only a....
Such integerprogramming algorithms are discussed by Padberg and in Beasley.
Integral linear programs
A linear program in real variables is said to be integral if it has at least one optimal solution which is integral. Likewise, a polyhedron is said to be integral if for all bounded feasible objective functions c, the linear program has an optimum with integer coordinates. As observed by Edmonds and Giles in 1977, one can equivalently say that a polyhedron is integral if for every bounded feasible integral objective function c, the optimal value of the linear progam is an integer.
Integral linear programs are of central importance in the polyhedral aspect of combinatorial optimizationCombinatorial optimizationIn applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible... since they provide an alternate characterization of a problem. Specifically, for any problem, the convex hull of the solutions is an integral polyhedron; if this polyhedron has a nice/compact description, then we can efficiently find the optimal feasible solution under any linear objective. Conversely, if we can prove that a linear programming relaxation is integral, then it is the desired description of the convex hull of feasible (integral) solutions.
Note that terminology is not consistent throughout the literature, so one should be careful to distinguish the following two concepts,
in an integer linear program, described in the previous section, variables are forcibly constrained to be integers, and this problem is NPhard in general,
in an integral linear program, described in this section, variables are not constrained to be integers but rather one has proven somehow that the continuous problem always has an integral optimal value (assuming c is integral), and this optimal value may be found efficiently since all polynomialsize linear programs can be solved in polynomial time.
One common way of proving that a polyhedron is integral is to show that it is totally unimodular. There are other general methods including the integer decomposition property and total dual integrality. Other specific wellknown integral LPs include the matching polytope, lattice polyhedra, submodular flow polyhedra, and the intersection of 2 generalized polymatroids/gpolymatroids  e.g. see Schrijver 2003.
A bounded integral polyhedron is sometimes called a convex lattice polytopeConvex lattice polytopeA convex lattice polytope is a geometric object playing an important role in discrete geometry and combinatorial commutative algebra. It is a polytope in a Euclidean space Rn which is a convex hull of finitely many points in the integer lattice Zn ⊂ Rn..., particularly in two dimensions.
Solvers and scripting (programming) languages
Free opensource permissivePermissive free software licenceA permissive free software licence is a class of free software licence with minimal requirements about how the software can be redistributed. This is in contrast to copyleft licences, which have reciprocity / sharealike requirements. Both sets of free software licences offer the same freedoms in... licenses:
Name
License
Brief info
OpenOptOpenOptOpenOpt is an opensource framework for numerical optimization, nonlinear equations and systems of them. It is licensed under the BSD license, making it available to be used in both open and closedcode software. The package already has some essential ....
BSDBSD licensesBSD licenses are a family of permissive free software licenses. The original license was used for the Berkeley Software Distribution , a Unixlike operating system after which it is named....
Universal crossplatform numerical optimization framework, see its LP page and other problems involved
pulpor
BSD
Python module for modeling and solving linear programming problems
Pyomo
BSD
Python module for formulating linear programming problems with abstract models
Free opensource copyleft (reciprocal)CopyleftCopyleft is a play on the word copyright to describe the practice of using copyright law to offer the right to distribute copies and modified versions of a work and requiring that the same rights be preserved in modified versions of the work... licenses:
Name
License
Brief info
LP_Solve
LGPL
Userfriendly linear and integer programming solver. Also provides DLL for program integration, and is compatible with GNU MathProg and Zimpl modelling languages.
Cassowary constraint solverCassowary constraint solverCassowary is an incremental constraint solving toolkit that efficiently solves systems of linear equalities and inequalities. Constraints may be either requirements or preferences...
LGPL
an incremental constraint solving toolkit that efficiently solves systems of linear equalities and inequalities.
CVXOPT
GPL
general purpose convex optimization solver written in Python, with a C API, and calls external routines (e.g. BLASBlasBlas is mainly a Spanish given name and surname, related to Blaise. It may refer toPlaces:*Piz Blas, mountain in Switzerland*San Blas , many places  see separate article, also**Cape San Blas Light, lighthouse..., LAPACKLAPACKExternal links:* : a modern replacement for PLAPACK and ScaLAPACK* on Netlib.org* * * : a modern replacement for LAPACK that is MultiGPU ready* on Sourceforge.net* * optimized LAPACK for Solaris OS on SPARC/x86/x64 and Linux* * *..., FFTWFFTWFFTW, for "Fastest Fourier Transform in the West", is a software library for computing discrete Fourier transforms , developed by Matteo Frigo and Steven G. Johnson at the Massachusetts Institute of Technology....) for numerical computations. Has its own solvers, but can also call glpk or MOSEK if installed
glpkGNU Linear Programming KitThe GNU Linear Programming Kit is a software package intended for solving largescale linear programming , mixed integer programming , and other related problems. It is a set of routines written in ANSI C and organized in the form of a callable library...
GPL
GNU Linear Programming Kit, a free LP/MILP solver. Uses GNU MathProg modelling language.
QocaQocaQoca is a GPL library for incrementally solving systems of linear equations with various goal functions. It contains a robust implementation of Cassowary, a popular linear programming algorithm for handling Manhattan goal functions. It is used in several free software projects and is maintained...
GPL
a library for incrementally solving systems of linear equations with various goal functions
CBC
CPLCommon Public LicenseIn computing, the CPL is a free software / opensource software license published by IBM. The Free Software Foundation and Open Source Initiative have approved the license terms of the CPL....
a MIP solver from COINORCOINORCOINOR, which stands for Computational Infrastructure for Operations Research, is a project that aims to "create for mathematical software what the open literature is for mathematical theory." The open literature provides the OR community with a peerreview process and an archive...
CLP
CPL
an LP solver from COINOR
RProject
GPL
a programming language and software environment for statistical computing and graphics
CVX
GPL
MATLAB based modeling system for convex optimization, including linear programs; calls either SDPT3 or SeDuMi as a solver
CVXMOD
GPL
Python based modeling system, similar to CVX. It calls CVXOPT as its solver. It is still in alpha release, as of 2009
SDPT3
GPL
MATLAB based convex optimization solver
SeDuMi
GPL
MATLAB based convex optimization solver
MINTOMINTOMINTO is an integer programming solver which uses branch and bound algorithm. It stands for Mixed Integer Optimizer.MINTO is a software system that solves mixed integer programming problem by a branch and bound algorithm with linear programming relaxations. It also provides automatic constraint... (Mixed Integer Optimizer, an integer programmingInteger programmingAn integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NPhard... solver which uses branch and bound algorithm) has publicly available source code but not open source.
Proprietary:Proprietary softwareProprietary software is computer software licensed under exclusive legal right of the copyright holder. The licensee is given the right to use the software under certain conditions, while restricted from other uses, such as modification, further distribution, or reverse engineering.Complementary...
Name
Brief info
APMonitorAPMonitorAPMonitor, or "Advanced Process Monitor", is a modeling language for differential and algebraic equations. It is used for describing and solving representations of physical systems in the form of implicit DAE models. APMonitor is suited for largescale problems and allows solutions of dynamic...
AIMMSAIMMSAIMMS is a software system designed for modeling and solving largescale optimization and schedulingtype problems....
AMPLAMPLAMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and solving highcomplexity problems for largescale mathematical computation AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and...
A popular modeling language for largescale linear, mixed integer and nonlinear optimisation with a free student version available.
Analytica
Optimization modeling software that incorporates stateoftheart algorithms for linear and nonlinear optimization. Supports LP, NLP, QP, continuous and integer optimization.
CPLEXCPLEXIBM ILOG CPLEX Optimization Studio is an optimization software package. In 2004, the work on CPLEX earned the first ....
Popular solver with an API for several programming languages, and also has a modelling language and works with AIMMS, AMPL, GAMSGeneral Algebraic Modeling SystemThe General Algebraic Modeling System is a highlevel modeling system for mathematical optimization. GAMS is designed for modeling and solving linear, nonlinear, and mixedinteger optimization problems. The system is tailored for complex, largescale modeling applications and allows the user to..., MPL, OpenOpt, OPL Development Studio, and TOMLABTOMLABThe TOMLAB Optimization Environment is a modeling platform for solving applied optimization problems in MATLAB.Description:TOMLAB is a general purpose development and modeling environment in MATLAB for research, teaching and practical solution of optimization problems...
EXCELExcelExcel may refer to:* Microsoft Excel, a spreadsheet application by Microsoft Corporation* Excel , a brand of chewing gum produced by Wrigley's* Excel , a crossover thrash/punk band from Venice, California... Solver Function
FinMath
A .NET.NET FrameworkThe .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability... numerical library containing an interiorpoint primaldualInterior point methodInterior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems.The interior point method was invented by John von Neumann... solver.
FortMPFortMPFortMP is a software package for solving largescale optimization problems. It solves linear programming problems, quadratic programming problems and mixed integer programming problems...
GAMSGeneral Algebraic Modeling SystemThe General Algebraic Modeling System is a highlevel modeling system for mathematical optimization. GAMS is designed for modeling and solving linear, nonlinear, and mixedinteger optimization problems. The system is tailored for complex, largescale modeling applications and allows the user to...
GIPALS
The maximum number of constraints and variables is unlimited. The linear program solver is based on InteriorPoint method (Mehrotra predictorcorrector algorithm) and optimized for large sparse linear programs by implementing the stateofart algorithm to order the constraints matrix. The user can specify the linear program using a set of exported DLL functions.
GurobiGurobiGurobi is a commercial software package for solving largescale linear optimization, quadratic optimization, and mixedinteger optimization problems...
Solver with parallel algorithms for largescale linear programs, quadratic programs and mixedinteger programs. Free for academic use.
IMSL Numerical LibrariesIMSL Numerical LibrariesIMSL is a commercial collection of software libraries of numerical analysis functionality that are implemented in the computer programming languages of C, Java, C#.NET, and Fortran...
Collections of math and statistical algorithms available in C/C++, Fortran, Java and C#/.NET. Optimization routines in the IMSL Libraries include unconstrained, linearly and nonlinearly constrained minimizations, and linear programming algorithms.
Lingo
LPL
LiPS (freeware)
Linear Program Solver (LiPS) is intended for solving linear programming problems. Main features: easy to use graphical interface, sensitivity analysis, goal and mixed integer programming solver. LiPS supports MPSMPS (format)MPS is a file format for presenting and archiving linear programming and mixed integer programming problems. Overview :... and simple LP format (like lpsolve).
MATLABMATLABMATLAB is a numerical computing environment and fourthgeneration programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...
A generalpurpose and matrixoriented programminglanguage for numerical computing. Linear programming in MATLAB requires the Optimization Toolbox in addition to the base MATLAB product; available routines include BINTPROG and LINPROG
MathematicaMathematicaMathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...
A generalpurpose programminglanguage for mathematics, including symbolic and numerical capabilities.
MOPS
MOSEKMOSEKMOSEK is a software package for the solution of linear, mixedinteger linear, quadratic, mixedinteger quadratic, quadratically constraint, conic and convex nonlinear mathematical optimization problems. The emphasize in MOSEK is on solving large scale sparse problems. Particularly the...
A solver for large scale optimization with API for several languages (C++,java,.net, Matlab and python).
NMath StatsNMath StatsNMath Stats is a statistical package for the Microsoft .NET Framework. It is developed by CenterSpace Software. Version 1.0 was released in December, 2003. The current version of NMath Stats is 3.2, released in July, 2010...
A generalpurpose .NET.NET FrameworkThe .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability... statistical library containing a simplex solver.
OptimJOptimJOptimJ is an extension of the Java with language support for writing optimization models and abstractions for bulk data processing. OptimJ aims at providing a clear and concise algebraic notation for optimization modeling, removing compatibility barriers between optimization modeling and...
A Javabased modeling language for optimization with a free version available.
SASSAS SystemSAS is an integrated system of software products provided by SAS Institute Inc. that enables programmers to perform:* retrieval, management, and mining* report writing and graphics* statistical analysis.../OR
A suite of solvers for Linear, Integer, Nonlinear, DerivativeFree, Network, Combinatorial and Constraint Optimization; the Algebraic modeling languageAlgebraic modeling languageAlgebraic Modeling Languages are highlevel computer programming languages for describing and solving high complexity problems for large scale mathematical computation... OPTMODEL; and a variety of vertical solutions aimed at specific problems/markets, all of which are fully integrated with the SAS SystemSAS SystemSAS is an integrated system of software products provided by SAS Institute Inc. that enables programmers to perform:* retrieval, management, and mining* report writing and graphics* statistical analysis....
SCIPSCIP (optimization software)SCIP is a mixed integer programming solver and a framework for Branch and cut and Branch and price, developed at Zuse Institute Berlin....
A generalpurpose constraint integer programming solver with an emphasis on MIP. Compatible with Zimpl modelling language. Free for academic use and available in source code.
Solver Foundation
A .NET platform for modeling, scheduling, and optimization.
SoPlex
The Sequential objectoriented simPlex: a generalpurpose LP solver. Free for academic use and available in source code.
SuanShu
A Javabased math library that supports linear programming and other kinds of numerical optimization.
TOMLAB
VisSimVisSimVisSim is a visual block diagram language for simulation of dynamical systems and model based design of embedded systems. It is developed by Visual Solutions of Westford, Massachusetts....
A visual block diagramBlock diagramBlock diagram is a diagram of a system, in which the principal parts or functions are represented by blocks connected by lines, that show the relationships of the blocks.... language for simulation of dynamical systemDynamical systemA dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...s.
Xpress
See also
Mathematical programmingMathematical ProgrammingMathematical Programming, established in 1971, and published by Springer Science+Business Media, is the official scientific journal of the Mathematical Optimization Society. It currently consists of two series: A and B. The "A" series contains general publications. The "B" series focuses on topical...
Nonlinear programmingNonlinear programmingIn mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
Convex programming
Dynamic programmingDynamic programmingIn mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
Simplex algorithmSimplex algorithmIn mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century...., used to solve LP problems
Quadratic programmingQuadratic programmingQuadratic programming is a special type of mathematical optimization problem. It is the problem of optimizing a quadratic function of several variables subject to linear constraints on these variables...., a superset of linear programming
Shadow priceShadow priceIn constrained optimization in economics, the shadow price is the instantaneous change per unit of the constraint in the objective value of the optimal solution of an optimization problem obtained by relaxing the constraint...
MPS file formatMPS (format)MPS is a file format for presenting and archiving linear programming and mixed integer programming problems. Overview :...
nl file formatNl (format)nl is a file format for presenting and archiving mathematical programming problems. It supports linear and nonlinear optimization problems as well as complementarity problems , in discrete or continuous variables...
MIP example, job shop problemJobshop problemThe jobshop problem is a problem in discrete or combinatorial optimization, and is a generalization of the famous travelling salesman problem...
Linearfractional programming (LFP)
Oriented matroidOriented matroidAn oriented matroid is a mathematical structure that abstracts the properties of directed graphs and of arrangements of vectors in a vector space over an ordered field...
Further reading
A reader may consider beginning with Nering and Tucker, with the first volume of Dantzig and Thapa, or with Williams.
Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Extensions, Universitext, SpringerVerlag, 2001. (Problems from Padberg with solutions.)
Chapter 4: Linear Programming: pp. 63–94. Describes a randomized halfplane intersection algorithm for linear programming. A6: MP1: INTEGER PROGRAMMING, pg.245. (computer science, complexity theory)
Bernd Gärtner, Jiří MatoušekJirí Matoušek (mathematician)Jiří Matoušek is a Czech mathematician working in computational geometry. He is a professor at Charles University in Prague and is the author of several textbooks and research monographs.... (2006). Understanding and Using Linear Programming, Berlin: Springer. ISBN 3540306978 (elementary introduction for mathematicians and computer scientists)
Cornelis Roos, Tamás Terlaky, JeanPhilippe Vial, Interior Point Methods for Linear Optimization, Second Edition, SpringerVerlag, 2006. (Graduate level)
Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0471982326 (mathematical)
Robert J. VanderbeiRobert J. VanderbeiRobert J. Vanderbei is an American mathematician and Professor in the Department of Operations Research and Financial Engineering at Princeton University.Biography:..., Linear Programming: Foundations and Extensions, 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. ISBN 9780387743875. (An online second edition was formerly available. Vanderbei's site still contains extensive materials.)
H. P. Williams, Model Building in Mathematical Programming, Third revised Edition, 1990. (Modeling)
Stephen J. Wright, 1997, PrimalDual InteriorPoint Methods, SIAM. (Graduate level)
Yinyu YeYinyu YeIn mathematical optimization, Yinyu Ye is a specialist in interior point methods, especially convex minimization and in linear programming. Ye is a professor of management science at Stanford University.Research publications:..., 1997, Interior Point Algorithms: Theory and Analysis, Wiley. (Advanced graduatelevel)
Ziegler, Günter M.Günter M. ZieglerGünter M. Ziegler is a German mathematician. Ziegler is known for his research in discrete mathematics and geometry, and particularly on the combinatorics of polytopes. Biography :..., Chapters 1–3 and 6–7 in Lectures on Polytopes, SpringerVerlag, New York, 1994. (Geometry)
External links
Guidance On Formulating LP Problems
Mathematical Programming Glossary
The Linear Programming FAQ
Benchmarks For Optimisation Software
2009 Linear Programming Software Survey  OR/MS Today
George Dantzig
ShowWikipediaFooter("Linear_programming")
}