Home Discussion Topics Dictionary Almanac

Signup Login

Linear programming

Discussion

Ask a question about 'Linear programming'

Start a new discussion about 'Linear programming'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In mathematics

Mathematics

Mathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....

, linear programming (LP) is a technique for optimization

Optimization (mathematics)

In mathematics, optimization, or mathematical programming, refers to choosing the best element from some set of available alternatives.In the simplest case, this means solving problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or...

of a linear

Linear

The word linear comes from the Latin word linearis, which means created by lines.In mathematics, a linear map or function f is a function which satisfies the following two properties......

objective function, subject to linear equality and linear inequality

Linear inequality

In mathematics a linear inequality is an inequality which involves a linear function.-Definitions:When operating in terms of real numbers, linear inequalities are the ones written in the forms or ,...

constraints

Constraint (mathematics)

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

. Informally, linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model

Mathematical model

A mathematical model uses mathematical language to describe a system. Mathematical models are used not only in the natural sciences and engineering disciplines but also in the social sciences ; physicists, engineers, computer scientists, and economists use...

and given some list of requirements represented as linear equations.

More formally, given a polytope

Polytope

In geometry, polytope is a generic term that can refer to a two-dimensional polygon, a three-dimensional polyhedron, or any of the various generalizations thereof, including generalizations to higher dimensions and other abstractions .When referring to an...

(for example, a polygon

Polygon

In geometry a polygon is traditionally a plane figure that is bounded by a closed path or circuit, composed of a finite sequence of straight line segments . These segments are called its edges or sides, and the points where two edges meet are the polygon's vertices or corners...

or a polyhedron

Polyhedron

A polyhedron is often defined as a geometric solid with flat faces and straight edges .This definition of a polyhedron is not very precise, and to a modern mathematician is...

), and a real

Real number

In mathematics, the real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339..., where the digits continue in some way; or, the real...

-valued affine function
defined on this polytope, a linear programming method will find a point in the polytope where this function has the smallest (or largest) value. Such points may not exist, but if they do, searching through the polytope vertices is guaranteed to find at least one of them.

Linear programs are problems that can be expressed in canonical form

Canonical form

Generally, in mathematics, a 'canonical form' of an object is a standard way of presenting that object....

Maximize

Subject to

represents the vector of variables (to be determined), while and are vectors of (known) coefficients and is a (known) matrix of coefficients. The expression to be maximized or minimized is called the objective function ( in this case). The equations are the constraints which specify a convex

Convex set

In 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. For example, a solid cube is convex, but anything that is hollow or has a dent in it, for example, a crescent shape, is not...

polytope

Polytope

over which the objective function is to be optimized.

Linear programming can be applied to various fields of study. Most extensively it is used in business and economic situations, but can also be utilized for some engineering problems. Some 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, assignment, and design.

History of linear programming

The problem of solving a system of linear inequalities dates back at least as far as Fourier

Joseph Fourier

Jean Baptiste Joseph Fourier was a French mathematician and physicist best known for initiating the investigation of Fourier series and their application to problems of heat transfer. The Fourier transform and Fourier's Law are also named in his honour...

, after whom the method of Fourier-Motzkin elimination is named. Linear programming arose as a mathematical model developed during the second world war

World War II

World War II, or the Second World War , was a global military conflict which involved a majority of the world's nations, including all great powers, organized into 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. It was kept secret until 1947. Postwar, many industries found its use in their daily planning.

The founders of the subject are Leonid Kantorovich

Leonid Kantorovich

Leonid Vitaliyevich Kantorovich was a Soviet/Russian mathematician and economist, known for his theory and development of techniques for the optimal allocation of resources. He was the winner of the Nobel Prize in Economics in 1975 and the only winner of this prize from the USSR.Kantorovich...

, a Russian mathematician who developed linear programming problems in 1939, George B. Dantzig

George Dantzig

George Bernard Dantzig was an American mathematician, and the Professor Emeritus of Transportation Sciences and Professor of Operations Research and of Computer Science at Stanford....

, who published the simplex method

Simplex algorithm

In mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerically solving linear programming problems...

in 1947, John von Neumann

John von Neumann

John von Neumann was a Hungarian American mathematician who made major contributions to a vast range of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, continuous geometry, economics and game theory, computer science, numerical analysis, hydrodynamics John...

, who developed the theory of the duality in the same year. The linear programming problem was first shown to be solvable in polynomial time by Leonid Khachiyan

Leonid Khachiyan

Leonid Genrikhovich Khachiyan was a Russian 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 Karmarkar

Narendra Karmarkar

Narendra 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 interior point method

Interior point method

Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems....

for solving linear programming 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 research

Operations research

Operations research or Quantitative management, as termed in the USA, Canada, South Africa and Australia, and operational research, as termed in Europe, is an interdisciplinary branch of applied mathematics that uses methods such as mathematical modeling, statistics, and algorithms to arrive at...

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 sub-problems. 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 microeconomics

Microeconomics

Microeconomics is a branch of economics that studies how households and firms make decisions to allocate limited resources, typically in 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 ever-changing, most companies would like to maximize profits or minimize costs with limited resources. Therefore, many issues can boil down to 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 three parts:

A linear function to be maximized

e.g. maximize

Problem constraints of the following form

e.g.

Non-negative variables

e.g.

The problem is usually expressed in matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, such asEntries of a matrix are often denoted by a variable with two subscripts, as shown on the right. Matrices of the same size can be added and subtracted entrywise and matrices of compatible size can be multiplied...

form, and then becomes:

maximize

subject to

Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variable

Variable (programming)

In computer programming, a variable is a facility for storing data. The current value of the variable is the data actually stored in the variable. Depending on the programming language in question, the data stored in the variable can be intentionally altered during the program run. This is why it...

s can always be rewritten into an equivalent problem in standard form.

Example

Suppose that a farmer has a piece of farm land, say A square kilometres large, to be planted with either wheat or barley or some combination of the two. The farmer has a limited permissible amount F of fertilizer and P of insecticide which can be used, each of which is required in different amounts per unit area for wheat (F₁, P₁) and barley (F₂, P₂). Let S₁ be the selling price of wheat, and S₂ the price of barley. If we denote the area planted with wheat and barley by x₁ and x₂ respectively, then the optimal number of square kilometres to plant with wheat vs barley can be expressed as a linear programming problem:

maximize		(maximize the revenue — revenue is the "objective function")
subject to		(limit on total area)
		(limit on fertilizer)
		(limit on insecticide)
		(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 algorithm

Simplex algorithm

In mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerically solving linear programming problems...

. This form introduces non-negative slack variable
Slack variable
In Linear programming a slack variable is a variable that is added to a constraint to turn the inequality into an equation.This is required to turn an inequality into an equality where a linear combination of variables is less than or equal to a given constant in the former...

s to replace inequalities with equalities in the constraints. The problem can then be written in the following block matrix

Block matrix

In the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a partition of a matrix into rectangular smaller matrices called blocks. Looking at it another way, the matrix is written in terms of smaller matrices written side-by-side...

form:

Maximize Z in:

where 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		(objective function)
subject to		(augmented constraint)
		(augmented constraint)
		(augmented constraint)

where are (non-negative) 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 in:

Duality

Every linear programming problem, referred to as a primal problem, can be converted into a dual problem

Dual problem

In linear programming, the primary problem and the dual problem are complementary. A solution to either one determines a solution to both.- Background :...

, which provides an upper bound to the optimal value of the primal problem. In matrix form, we can express the primal problem as:

maximize

subject to

The corresponding dual problem is:

minimize

subject to

where y is used instead of x as variable vector.

There are two ideas fundamental to duality theory. One is the fact that 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^Tx*=b^Ty*.

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 A 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), for wheat and for barley. This corresponds to the following linear programming problem:

minimize		(minimize the total cost of the means of production as the "objective function")
subject to		(the farmer must receive no less than for his wheat)
		(the farmer must receive no less than for his barley)
		(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.

Covering-Packing Dualities

A covering LP

Covering problem

In 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

subject to

such that the matrix and the vectors and are non-negative.

The dual of a covering LP is a packing LP

Packing problem

Packing problems are one area where mathematics meets puzzles . Many of these problems stem from real-life problems with packing items.In a packing problem, you are given:...

, a linear program of the form

maximize

subject to

such that the matrix and the vectors and are non-negative.

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 relaxation of set packing problem

Set packing

Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems....

, independent set problem

Independent set problem

In mathematics, the independent set problem is a well-known problem in graph theory. The independent set problem is known to be NP-complete. It is closely related to the clique problem.- Description :...

, or matching is a packing LP. The LP relaxation of set cover problem

Set cover problem

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

, vertex cover problem, or dominating set problem

Dominating set problem

-Definition:An instance of the dominating set problem consists of:* a graph G with a set V of vertices and a set E of edges, and* a positive integer K smaller than or equal to the number of vertices in G....

is a covering LP.

Finding a fractional coloring

Fractional coloring

Fractional 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 graph

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

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

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₁, x₂, . . ., x_n) is primal feasible and that y = (y₁, y₂, . . . , y_m) is dual feasible. Let (w₁, w₂, . . ., w_m) denote the corresponding primal slack variables, and let (z₁, z₂, . . . , z_n) denote the corresponding dual slack variables. Then x and y are optimal for their respective problems if and only if
x_jz_j = 0, for j = 1, 2, . . . , n,
w_iy_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 non-negativity constraint requirement , i.e., the price is not zero, then there must scarce supplies (no "leftovers").

Theory

Geometrically, the linear constraints define a convex

Convex set

polytope

Polytope

, which is called the feasible region. It is not hard to see that every local optimum (a point x such that for every unit direction vector d with positive objective value any every it holds that is infeasible) is also a global optimum. This holds more generally for convex programs: see the KKT

Karush-Kuhn-Tucker conditions

In mathematics, the Karush–Kuhn–Tucker conditions are necessary for a solution in nonlinear programming to be optimal, provided some regularity conditions are satisfied. It is a generalization of the method of Lagrange multipliers to inequality constraints. The conditions are named for William...

theorem.

There are two situations in which no optimal solution can be found. First, if the constraints contradict each other (for instance, x ≥ 2 and x ≤ 1) then the feasible region is empty and there can be no optimal solution, since there are no solutions at all. In this case, the LP is said to be infeasible.

Alternatively, the polyhedron

Polyhedron

A polyhedron is often defined as a geometric solid with flat faces and straight edges .This definition of a polyhedron is not very precise, and to a modern mathematician is...

can be unbounded in the direction of the objective function (for example: maximize x₁ + 3 x₂ subject to x₁ ≥ 0, x₂ ≥ 0, x₁ + x₂ ≥ 10), in which case there is no optimal solution since solutions with arbitrarily high values of the objective function can be constructed.

Barring these two conditions (which can often be ruled out when dealing with specific LPs), the optimum is always attained at a vertex of the polyhedron (unless the polyhedron has no vertices, for example in the feasible bounded linear program ; polyhedra with at least one vertex are called pointed). However, the optimum is not necessarily unique: it is possible to have a set of optimal solutions covering an edge or face of the polyhedron, or even the entire polyhedron (this last situation would occur if the objective function were constant on the polyhedron).

The vertices of the polyhedron are also called basic feasible solutions. The reason for this choice of name is as follows. Let d denote the dimension, i.e. the number of variables. Then the following theorem holds: for every vertex x* of the LP feasible region, there exists a set of d 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 universe), rather than the continuous universe of LP solutions. This principle underlies the simplex algorithm

Simplex algorithm

In mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerically solving linear programming problems...

for solving linear programs.

Algorithms

The simplex algorithm

Simplex algorithm

In mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerically solving linear programming problems...

, developed by George Dantzig

George Dantzig

George Bernard Dantzig was an American mathematician, and the Professor Emeritus of Transportation Sciences and Professor of Operations Research and of Computer Science at Stanford....

, solves LP problems by constructing an admissible solution at a vertex of the polyhedron and then walking along edges of the polyhedron to vertices with successively higher values of the objective function until the optimum is reached. Although this algorithm

Algorithm

In mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....

is quite efficient in practice and can be guaranteed to find the global optimum if certain precautions against cycling are taken, it has poor worst-case behavior: it is possible to construct a linear programming problem 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

Polynomial time

In computer science, polynomial time refers to the running time of an algorithm, that is, the number of computation steps a computer or an abstract machine requires to evaluate the algorithm....

(complexity class P

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes...

).

This long standing issue was resolved by Leonid Khachiyan

Leonid Khachiyan

in 1979 with the introduction of the ellipsoid method

Ellipsoid method

The ellipsoid method is an algorithm for solving convex optimization problems. It was introduced by Naum Z. Shor, Arkady Nemirovsky, and David B. Yudin in 1972, and used by Leonid Khachiyan to prove the polynomial-time solvability of linear programs. At the time, the ellipsoid method was the only...

, the first worst-case polynomial-time algorithm for linear programming. To solve a problem which has n variables and can be encoded in L input bits, this algorithm uses O(n⁴L) arithmetic operations on numbers with O(L) digits. It consists of a specialization of the nonlinear optimization

Nonlinear programming

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

technique developed by Naum Z. Shor

Naum Z. Shor

Naum Zuselevich Shor was a Ukrainian mathematician specializing in optimization.He made significant contributions to nonlinear and stochastic programming, numerical techniques for non smooth optimization, discrete optimization problems, matrix optimization, dual quadratic bounds in multi-extremal...

, generalizing the ellipsoid method for convex optimization

Convex optimization

Convex optimization is a subfield of mathematical optimization, which is concerned with minimizing convex functions. Given a real vector space together with a convex, real-valued function...

proposed by Arkadi Nemirovski, a 2003 John von Neumann Theory Prize

John von Neumann Theory Prize

The John von Neumann Theory Prize of the Institute for Operations Research and the Management Sciencesis awarded annually to an individual who has made fundamental and sustained contributions to theory in operations research and the management sciences.The Prize named after mathematician John von...

winner, and D. Yudin.

Khachiyan's algorithm was of landmark importance for establishing the polynomial-time solvability of linear programs. The algorithm had little practical impact, as the simplex method is more efficient for all but specially constructed families of linear programs. However, it inspired new lines of research in linear programming with the development of interior point method

Interior point method

Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems....

s, which can be implemented as a practical tool. In contrast to the simplex algorithm, which finds the optimal solution by progressing along points on the boundary of a polyhedral set, interior point methods move through the interior of the feasible region.

In 1984, N. Karmarkar

Narendra Karmarkar

Narendra K. Karmarkar is an Indian mathematician, renowned for developing Karmarkar's algorithm. He is listed as an ISI highly cited researcher.- Biography :...

proposed a new interior point projective method for linear programming. Karmarkar's algorithm

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

not only improved on Khachiyan's theoretical worst-case polynomial bound (giving ), but also promised dramatic practical performance improvements over the simplex method. Since then, many interior point methods have been proposed and analyzed. Early successful implementations were based on affine scaling variants of the method. For both theoretical and practical properties, barrier function

Barrier function

In 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 path-following methods are the most common recently.

In 1985 Bruni represented the LP problem as a fixed-point problem and considered solution methods; in 1992 Abdullah derived a similar representation and a regression solution method.

The current opinion is that the efficiency of good implementations of simplex-based methods and interior point methods is similar for routine applications of linear programming.

LP solvers are in widespread use for optimization of various problems in industry, such as optimization of flow in transportation networks, many of which can be transformed into linear programming problems only with some difficulty.

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 large-scale linear programs.

Does LP admit a strongly polynomial-time 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 Smale

Stephen 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 . He entered the University of Michigan in 1948...

as among the 18 greatest unsolved problems

Smale's problems

Smale's problems refers to a list of eighteen unsolved problems in mathematics, 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 methods

Ellipsoid method

and interior-point techniques

Interior point method

Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems....

, no algorithms have yet been found that allow strongly polynomial-time 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.

Are there pivot rules which lead to polynomial-time Simplex variants?
Do all polyhedral graphs have polynomially-bounded diameter?
Is the Hirsch conjecture
Hirsch conjecture
In mathematical programming and polyhedral combinatorics, Hirsch's conjecture states that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d...

true for polyhedral graphs?

These questions relate to the performance analysis and development of Simplex-like methods. The immense efficiency of the Simplex algorithm in practice despite its exponential-time 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 edge-following algorithms, so named because they solve linear programming problems by moving from vertex to vertex along edges of a polyhedron. This means that their theoretical performance is limited by the maximum number of edges between any two vertices on the LP polyhedron. As a result, we are interested in knowing the maximum graph-theoretical diameter of polyhedral graphs

Graph (mathematics)

. It has been proved that all polyhedra have subexponential diameter, and all experimentally observed polyhedra have linear diameter, it is presently unknown whether any polyhedron has superpolynomial or even superlinear diameter. If any such polyhedra exist, then no edge-following variant can run in polynomial or linear time, respectively. Questions about polyhedron diameter are of independent mathematical interest.

Simplex pivot methods preserve primal (or dual) feasibility. On the other hand, criss-cross pivot methods do not preserve (primal or dual) feasibility --- they may visit primal feasible, dual feasible or primal-and-dual 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 polyhedral graphs, graphs of arrangement polytopes are known to have small diameter, allowing the possibility of strongly polynomial-time criss-cross pivot method without resolving questions about the diameter of general polyhedra.

Integer unknowns

If the unknown variables are all required to be integers, then the problem is called an integer programming

Integer programming

An integer programming problem is any mathematical optimization or feasibility program in which some or all of the variables are restricted to be integral. In many settings the term integer program is used as short-hand for integer linear programming....

(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) NP-hard

NP-hard

NP-hard , 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 NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

. 0-1 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 NP-hard

NP-hard

, and in fact the decision version was one of Karp's 21 NP-complete problems

Karp's 21 NP-complete problems

One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NP-complete 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 NP-hard

NP-hard

.

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 right-hand sides of the constraints are integers.

Advanced algorithms for solving integer linear programs include:

cutting-plane method
Cutting-plane method
In mathematical optimization, the cutting-plane 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 bound
Branch and bound
Branch and bound is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization...
branch and cut
Branch and cut
Branch 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 price
if the problem has some extra structure, it may be possible to apply delayed column generation
Delayed column generation
Delayed 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 non-basic and assume a value of zero in the optimal solution, only a...

.

Solvers and scripting (programming) languages

Free and opensource:

Name	License	Brief info
LP_Solve	LGPL	User-friendly linear and integer programming solver. Also provides DLL for program integration.
Cassowary constraint solver Cassowary constraint solver Cassowary 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. BLAS Blas -Places:Piz Blas, mountain in SwitzerlandSan Blas, many places - see separate article, alsoCape San Blas Light, lighthouseChurch San Blas de Illescas of Coamo, church in Puerto Rico... , LAPACK LAPACK LAPACK is a software library for numerical linear algebra. It provides routines for solving systems of linear equations and linear least squares, eigenvalue problems, and singular value decomposition. It also includes routines to implement the associated matrix factorizations such as LU, QR,... , FFTW FFTW FFTW, 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
glpk GNU Linear Programming Kit The GNU Linear Programming Kit is a software package intended for solving large-scale 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
OpenOpt OpenOpt OpenOpt is a free optimization framework that was created in June 2007. It is a relatively new project that is developed in the of the at the National Academy of Sciences of Ukraine. OpenOpt interfaces with many different algorithms for solving , some of which are written in C or Fortran...	BSD BSD licenses BSD licenses represent a family of permissive free software licenses. The original was used for the Berkeley Software Distribution , a Unix-like operating system after which the license is named. The original owners of BSD were the Regents of the University of California because BSD was first...	Universal cross-platform numerical optimization framework; see its LP page and other problems involved
pulp-or	BSD BSD licenses BSD licenses represent a family of permissive free software licenses. The original was used for the Berkeley Software Distribution , a Unix-like operating system after which the license is named. The original owners of BSD were the Regents of the University of California because BSD was first...	Python module for modeling and solving linear programming problems
Qoca Qoca Qoca 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
CLP	CPL Common Public License In computing, the CPL is a free software / open-source software license published by IBM. The Free Software Foundation and Open Source Initiative have approved the license terms of the CPL....	an LP solver from COIN-OR COIN-OR COIN-OR stands for the Computational Infrastructure for Operations Research. The stated goal of the COIN-OR project is "to create for mathematical software what the open literature is for mathematical theory." The open literature provides the OR community with a peer-review process and an archive... project
R-Project	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 in alpha release, as of 2009
SDPT3	GPL	MATLAB based convex optimization solver
SeDuMi	GPL	MATLAB based convex optimization solver
YALMIP		MATLAB based modeling system for convex optimization, including linear programs; relies on external solvers. For LP, it can call free solvers, such as CDD, glpk GNU Linear Programming Kit The GNU Linear Programming Kit is a software package intended for solving large-scale 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... , LP_Solve, and QSOPT, or it can call commercial solvers such as MATLAB's BINTPROG or LINPROG (it can also call more general purpose solvers, such as SDPT3 or SeDuMi, which are also able to solve LP)

MINTO

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

| here
Mixed Integer Optimizer (an integer programming

Integer programming

solver which uses branch and bound algorithm) has publicly available source code
but not open source.
Commercial:

Name	Brief info
APMonitor APMonitor APMonitor, 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...
AIMMS
AMPL
CPLEX CPLEX ILOG CPLEX is an optimization software package. It is named for the simplex method and the C programming language, although today it contains interior point methods and interfaces in the C++ , C#, and Java languages...	Popular solver with an API for several programming language, and also has a modelling language and works with TOMLAB
EXCEL Excel Excel may refer to:* Microsoft Excel, a spreadsheet application by Microsoft Corporation* Excel , a brand of chewing gum produced by Wrigley's* Excel , a band from Venice, California... Solver Function
GAMS General Algebraic Modeling System The General Algebraic Modeling System is a high-level modeling system for mathematical programming and optimization. GAMS is designed for modeling linear, nonlinear and mixed integer optimization problems. The system is tailored for complex, large-scale modeling applications and allows the user to...
GIPALS
Gurobi Gurobi Gurobi is a commercial software package for solving large-scale mixed-integer linear optimization problems. Gurobi is named for its founders: Zonghao Gu, Edward Rothberg and Robert Bixby; Bixby was also the founder of CPLEX, while Rothberg and Gu led the CPLEX development team for nearly a...
IMSL Numerical Libraries IMSL Numerical Libraries IMSL 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. A Python interface is also available.The IMSL Libraries are provided by Visual Numerics Inc...	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 Lingo Lingo may refer to:* LINGO Modeling Language* Lingo , one of several unrelated programming languages* Lingo * Lingo * Lingo...
MATLAB MATLAB MATLAB is a numerical computing environment and fourth generation programming language. Developed by The MathWorks, MATLAB allows matrix manipulation, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs in other languages...	A general purpose mathematical programming language. Linear programming in MATLAB equires the Optimization Toolbox in addition to the base MATLAB product; available routines include BINTPROG and LINPROG
Mathematica Mathematica Mathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...	A general purpose mathematical programming language.
MOPS
MOSEK
OptimJ
SAS SAS System SAS is an integrated system of software products provided by SAS Institute that enables the programmer to perform:data entry, retrieval, management, and miningreport writing and graphics...
TOMLAB TOMLAB The 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...
Xpress-MP

Linear programming

History of linear programming

Uses

Standard form

Example

Augmented form (slack form)

Example

Duality

Example

Covering-Packing Dualities

Examples

Complementary slackness

Theory

Algorithms

Open problems and recent work

Integer unknowns

Solvers and scripting (programming) languages

See also

Further reading

External links