HOME

TheInfoList




Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a
mathematical model A mathematical model is a description of a system A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. A system, surrounded and influenced by its environm ...
whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as
mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimization problems of sorts arise i ...
). More formally, linear programming is a technique for the
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimization problems of sorts arise i ...
of a
linear Linearity is the property of a mathematical relationship (''function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out se ...

linear
objective function In mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimizat ...
, subject to
linear equality In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
and
linear inequality In mathematics a linear inequality is an inequality (mathematics), inequality which involves a linear function. A linear inequality contains one of the symbols of inequality:. It shows the data which is not equal in graph form. * greater than * ...
constraints. Its
feasible region In mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optim ...

feasible region
is a
convex polytope A convex polytope is a special case of a polytope In elementary geometry Geometry (from the grc, γεωμετρία; ''wikt:γῆ, geo-'' "earth", ''wikt:μέτρον, -metron'' "measurement") is, with arithmetic, one of the oldest branc ...
, which is a set defined as the
intersection In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities ...
of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a
real Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * Real (L'Arc-en-Ciel album), ''Real'' (L'Arc-en-Ciel album) (2000) * Real ...
-valued affine (linear) function defined on this polyhedron. A linear programming
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

algorithm
finds a point in the
polytope In elementary geometry Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, shape, size, and relativ ...
where this function has the smallest (or largest) value if such a point exists. Linear programs are problems that can be expressed in
canonical form In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
as : \begin & \text && \mathbf \\ & \text && \mathbf^T \mathbf\\ & \text && A \mathbf \leq \mathbf \\ & \text && \mathbf \ge \mathbf. \end Here the components of x are the variables to be determined, c and b are given
vectors Vector may refer to: Biology *Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism; a disease vector *Vector (molecular biology), a DNA molecule used as a vehicle to artificially carr ...
(with \mathbf^T indicating that the coefficients of c are used as a single-row matrix for the purpose of forming the matrix product), and ''A'' is a given
matrix Matrix or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols, or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the material in between a eukaryot ...
. The function whose value is to be maximized or minimized (\mathbf x\mapsto\mathbf^T\mathbf in this case) is called the
objective function In mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimizat ...
. The inequalities ''A''x ≤ b and x ≥ 0 are the constraints which specify a
convex polytope A convex polytope is a special case of a polytope In elementary geometry Geometry (from the grc, γεωμετρία; ''wikt:γῆ, geo-'' "earth", ''wikt:μέτρον, -metron'' "measurement") is, with arithmetic, one of the oldest branc ...
over which the objective function is to be optimized. In this context, two vectors are comparable when they have the same dimensions. If every entry in the first is less-than or equal-to the corresponding entry in the second, then it can be said that the first vector is less-than or equal-to the second vector. Linear programming can be applied to various fields of study. It is widely used in mathematics, and to a lesser extent in business,
economics Economics () is a social science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services. Economics focuses on the behaviour and interact ...

economics
, and for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proven useful in modeling diverse types of problems in
planning Planning is the process A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic. Things called a process include: Business and management *Business process A business p ...
,
routing Routing is the process of selecting a path for traffic in a Network theory, network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit switching, circuit-switched networks, such as ...

routing
,
scheduling A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible task (project management), tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order ...
, assignment, and design.


History

The problem of solving a system of linear inequalities dates back at least as far as
Fourier
Fourier
, who in 1827 published a method for solving them, and after whom the method of
Fourier–Motzkin elimination Fourier–Motzkin elimination, also known as the FME method, is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can output real number, real solutions. The algorithm is named after Joseph Fourier who pro ...
is named. In 1939 a linear programming formulation of a problem that is equivalent to the general linear programming problem was given by the
Soviet The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a socialist state A socialist state, socialist republic, or socialist country, sometimes referred to as a workers' state or workers' republic, is a sove ...
mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces ...

mathematician
and
economist An economist is a professional and practitioner in the social science Social science is the branch A branch ( or , ) or tree branch (sometimes referred to in botany Botany, also called , plant biology or phytology, is the s ...

economist
Leonid Kantorovich Leonid Vitaliyevich Kantorovich ( rus, Леони́д Вита́льевич Канторо́вич, , p=lʲɪɐˈnʲit vʲɪˈtalʲjɪvʲɪtɕ kəntɐˈrovʲɪtɕ, a=Ru-Leonid_Vitaliyevich_Kantorovich.ogg; 19 January 19127 April 1986) was a Sovie ...
, who also proposed a method for solving it. It is a way he developed, during
World War II World War II or the Second World War, often abbreviated as WWII or WW2, was a global war A world war is "a war War is an intense armed conflict between states State may refer to: Arts, entertainment, and media Literatur ...
, to plan expenditures and returns in order to reduce costs of the army and to increase losses imposed on the enemy. Kantorovich's work was initially neglected in the
USSR The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a socialist state that spanned Eurasia during its existence from 1922 to 1991. It was nominally a Federation, federal union of multiple national Republics of ...

USSR
. About the same time as Kantorovich, the Dutch-American economist T. C. Koopmans formulated classical economic problems as linear programs. Kantorovich and Koopmans later shared the 1975
Nobel prize in economics The Nobel Memorial Prize in Economic Sciences, officially the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel ( sv, Sveriges riksbanks pris i ekonomisk vetenskap till Alfred Nobels minne), is an economics award administered ...
. In 1941,
Frank Lauren Hitchcock Frank Lauren Hitchcock (March 6, 1875 – May 31, 1957) was an United States, American mathematician and physicist known for his formulation of the transportation problem in 1941. Academic life Frank did his preparatory study at Phillips Andover ...
also formulated transportation problems as linear programs and gave a solution very similar to the later
simplex method In optimization (mathematics), mathematical optimization, George Dantzig, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was s ...
. Hitchcock had died in 1957 and the Nobel prize is not awarded posthumously. During 1946–1947, George B. Dantzig independently developed general linear programming formulation to use for planning problems in the US Air Force. In 1947, Dantzig also invented the
simplex method In optimization (mathematics), mathematical optimization, George Dantzig, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was s ...
that for the first time efficiently tackled the linear programming problem in most cases. When Dantzig arranged a meeting with
John von Neumann John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American Hungarian Americans (Hungarian language, Hungarian: ''amerikai magyarok'') are United States, Americans of Hungarian p ...

John von Neumann
to discuss his simplex method, Neumann immediately conjectured the theory of duality by realizing that the problem he had been working in
game theory Game theory is the study of mathematical model A mathematical model is a description of a system A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. ...
was equivalent. Dantzig provided formal proof in an unpublished report "A Theorem on Linear Inequalities" on January 5, 1948. Dantzig's work was made available to public in 1951. In the post-war years, many industries applied it in their daily planning. Dantzig's original example was to find the best assignment of 70 people to 70 jobs. 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 The particle number (or number of particles) of a thermodynamic system A thermodynamic system is a body of matter In classical physics and general chemistry, matter is any substance that has mass and takes up space by having volume. All eve ...
in the
observable universe The observable universe is a ball-shaped region of the universe The universe ( la, universus) is all of space and time and their contents, including planets, stars, galaxy, galaxies, and all other forms of matter and energy. The Big Bang th ...
. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the
simplex algorithm In mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimi ...
. The theory behind linear programming drastically reduces the number of possible solutions that must be checked. The linear programming problem was first shown to be solvable in polynomial time by
Leonid Khachiyan Leonid Genrikhovich Khachiyan (; russian: Леонид Генрихович Хачиян; May 3, 1952April 29, 2005) was a Soviet and American mathematician and computer scientist A computer scientist is a person who has acquired the knowledg ...
in 1979, but a larger theoretical and practical breakthrough in the field came in 1984 when
Narendra Karmarkar Narendra Krishna Karmarkar (born circa 1956) is an India India, officially the Republic of India (Hindi Hindi (Devanagari: , हिंदी, ISO 15919, ISO: ), or more precisely Modern Standard Hindi (Devanagari: , ISO 15919, IS ...

Narendra Karmarkar
introduced a new
interior-point method Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 19 ...
for solving linear-programming problems.


Uses

Linear programming is a widely used field of optimization for several reasons. Many practical problems in operations research 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 was heavily used in the early formation of
microeconomics Microeconomics is a branch of mainstream economics Mainstream economics is the body of knowledge, theories, and models of economics, as taught by universities worldwide, that are generally accepted by economists as a basis for discussion. Als ...
and it is currently utilized in company management, such as planning, production, transportation, technology and other issues. Although the modern management issues are ever-changing, most companies would like to and minimize costs with limited resources. Google uses linear programming to stabilize YouTube videos. 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 three parts: * A linear function to be maximized : e.g. f(x_,x_) = c_1 x_1 + c_2 x_2 * Problem constraints of the following form : e.g. :: \begin a_ x_1 + a_ x_2 &\leq b_1 \\ a_ x_1 + a_ x_2 &\leq b_2 \\ a_ x_1 + a_ x_2 &\leq b_3 \\ \end * Non-negative variables : e.g. :: \begin x_1 \geq 0 \\ x_2 \geq 0 \end The problem is usually expressed in ''
matrix Matrix or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols, or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the material in between a eukaryot ...
form'', and then becomes: : \max \ Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variables can always be rewritten into an equivalent problem in standard form.


Example

Suppose that a farmer has a piece of farm land, say ''L'' km2, to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, ''F'' kilograms, and pesticide, ''P'' kilograms. Every square kilometer of wheat requires ''F''1 kilograms of fertilizer and ''P''1 kilograms of pesticide, while every square kilometer of barley requires ''F''2 kilograms of fertilizer and ''P''2 kilograms of pesticide. Let S1 be the selling price of wheat per square kilometer, and S2 be the selling 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: In matrix form this becomes: : maximize \begin S_1 & S_2 \end \begin x_1 \\ x_2 \end : subject to \begin 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end \begin x_1 \\ x_2 \end \le \begin L \\ F \\ P \end, \, \begin x_1 \\ x_2 \end \ge \begin 0 \\ 0 \end.


Augmented form (slack form)

Linear programming problems can be converted into an ''augmented form'' in order to apply the common form of the
simplex algorithm In mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimi ...
. This form introduces non-negative ''
slack variable In an optimization problem In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geom ...
s'' to replace inequalities with equalities in the constraints. The problems can then be written in the following
block matrix In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
form: : Maximize z: : \begin 1 & -\mathbf^T & 0 \\ 0 & \mathbf & \mathbf \end \begin z \\ \mathbf \\ \mathbf \end = \begin 0 \\ \mathbf \end :\mathbf \ge 0, \mathbf \ge 0 where \mathbf are the newly introduced slack variables, \mathbf are the decision variables, and z is the variable to be maximized.


Example

The example above is converted into the following augmented form: : where x_3, x_4, x_5 are (non-negative) slack variables, representing in this example the unused area, the amount of unused fertilizer, and the amount of unused pesticide. In matrix form this becomes: : Maximize z: : \begin 1 & -S_1 & -S_2 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & F_1 & F_2 & 0 & 1 & 0 \\ 0 & P_1 & P_2 & 0 & 0 & 1 \\ \end \begin z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end = \begin 0 \\ L \\ F \\ P \end, \, \begin x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end \ge 0.


Duality

Every linear programming problem, referred to as a ''primal'' problem, can be converted into a
dual problem In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. The solution to the dual problem provides a lowe ...
, which provides an upper bound to the optimal value of the primal problem. In matrix form, we can express the ''primal'' problem as: : Maximize cTx subject to ''A''x ≤ b, x ≥ 0; :: with the corresponding symmetric dual problem, : Minimize bTy subject to ''A''Ty ≥ c, y ≥ 0. An alternative primal formulation is: : Maximize cTx subject to ''A''x ≤ b; :: with the corresponding asymmetric dual problem, : Minimize bTy subject to ''A''Ty = 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 In applied mathematics, weak duality is a concept in optimization which states that the duality gap is always greater than or equal to 0. That means the solution to the dual (minimization) problem is ''always'' greater than or equal to the solution ...
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 Strong duality is a condition in optimization, mathematical optimization in which the primal optimal objective and the Duality (optimization), dual optimal objective are equal. This is as opposed to weak duality (the primal problem has optimal valu ...
theorem states that if the primal has an optimal solution, x*, then the dual also has an optimal solution, y*, and cTx*=bTy*. 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
dual linear program The dual of a given linear program (LP) is another LP that is derived from the original (the primal) LP in the following schematic way: * Each variable in the primal LP becomes a constraint in the dual LP; * Each constraint in the primal LP becomes ...
for details and several more examples.


Variations


Covering/packing dualities

A covering LP is a linear program of the form: : Minimize: bTy, : subject to: ''A''Ty ≥ c, y ≥ 0, such that the matrix ''A'' and the vectors b and c are non-negative. The dual of a covering LP is a packing LP, a linear program of the form: : Maximize: cTx, : subject to: ''A''x ≤ b, x ≥ 0, such that the matrix ''A'' and the vectors b and c are non-negative.


Examples

Covering and packing LPs commonly arise as a
linear programming relaxation In mathematics, the relaxation of a Mixed integer linear programming, (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are o ...
of a combinatorial problem and are important in the study of
approximation algorithms In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , an ...
. For example, the LP relaxations of the set packing problem, the
independent set problem In graph theory, an independent set, stable set, coclique or anticlique is a set of vertex (graph theory), vertices in a Graph (discrete mathematics), graph, no two of which are adjacent. That is, it is a set S of vertices such that for every tw ...
, and the are packing LPs. The LP relaxations of the
set cover problem The set cover problem is a classical question in combinatorics, computer science, operations research, and Computational complexity theory, complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. It is a prob ...
, the
vertex cover problem In graph theory, a vertex cover (sometimes node cover) of a Graph (discrete mathematics), graph is a set of Vertex (graph theory), vertices that includes at least one endpoint of every Edge (graph theory), edge of the graph (discrete mathematics) ...
, and the dominating set problem are also covering LPs. Finding a
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 vert ...
of a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
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 = (x1, x2, ... , x''n'') is primal feasible and that y = (y1, y2, ... , y''m'') is dual feasible. Let (w1, w2, ..., w''m'') denote the corresponding primal slack variables, and let (z1, z2, ... , 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 ''i''-th slack variable of the primal is not zero, then the ''i''-th variable of the dual is equal to zero. Likewise, if the ''j''-th slack variable of the dual is not zero, then the ''j''-th 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 be scarce supplies (no "leftovers").


Theory


Existence of optimal solutions

Geometrically, the linear constraints define the
feasible region In mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optim ...

feasible region
, which is a
convex Convex means curving outwards like a sphere, and is the opposite of concave. Convex or convexity may refer to: Science and technology * Convex lens A lens is a transmissive optics, optical device which focuses or disperses a light beam by me ...

convex
polyhedron In geometry Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, shape, size, and relative position o ...
. A
linear function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
is a
convex function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

convex function
, which implies that every
local minimum In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function (mathematics), function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, e ...
is a
global minimum In mathematical analysis Analysis is the branch of mathematics dealing with Limit (mathematics), limits and related theories, such as Derivative, differentiation, Integral, integration, Measure (mathematics), measure, sequences, Series (math ...
; similarly, a linear function is a
concave function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

concave function
, which implies that every
local maximum In mathematical analysis Analysis is the branch of mathematics dealing with Limit (mathematics), limits and related theories, such as Derivative, differentiation, Integral, integration, Measure (mathematics), measure, sequences, Series (math ...

local maximum
is a
global maximum In mathematical analysis Analysis is the branch of mathematics dealing with Limit (mathematics), limits and related theories, such as Derivative, differentiation, Integral, integration, Measure (mathematics), measure, sequences, Series (math ...
. An optimal solution need not exist, for two reasons. First, if the constraints are inconsistent, then no feasible solution exists: For instance, the constraints x ≥ 2 and x ≤ 1 cannot be satisfied jointly; in this case, we say that the LP is ''infeasible''. Second, when the
polytope In elementary geometry Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, shape, size, and relativ ...
is unbounded in the direction of the gradient of the objective function (where the gradient of the objective function is the vector of the coefficients of the objective function), then no optimal value is attained because it is always possible to do better than any finite value of the objective function.


Optimal vertices (and rays) of polyhedra

Otherwise, if a feasible solution exists and if the constraint set is bounded, then the optimum value is always attained on the boundary of the constraint set, by the ''
maximum principle In the mathematical fields of partial differential equations and geometric analysis, the maximum principle is any of a collection of results and techniques of fundamental importance in the study of elliptic partial differential equation, elliptic ...
'' for ''
convex function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

convex function
s'' (alternatively, by the ''minimum'' principle for ''
concave function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

concave function
s'') since linear functions are both convex and concave. However, some problems have distinct optimal solutions; for example, the problem of finding a feasible solution to a system of linear inequalities is a linear programming problem in which the objective function is the zero function (that is, the constant function taking the value zero everywhere). For this feasibility problem with the zero-function for its objective-function, if there are two distinct solutions, then every convex combination of the solutions is a solution. The vertices of the polytope are also called ''basic feasible solutions''. The reason for this choice of name is as follows. Let ''d'' denote the number of variables. Then the fundamental theorem of linear inequalities implies (for feasible problems) that for every vertex x* of the LP feasible region, there exists a set of ''d'' (or fewer) inequality constraints from the LP such that, when we treat those ''d'' constraints as equalities, the unique solution is x*. Thereby we can study these vertices by means of looking at certain subsets of the set of all constraints (a discrete set), rather than the continuum of LP solutions. This principle underlies the
simplex algorithm In mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimi ...
for solving linear programs.


Algorithms


Basis exchange algorithms


Simplex algorithm of Dantzig

The
simplex algorithm In mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimi ...
, developed by
George Dantzig George Bernard Dantzig (; November 8, 1914 – May 13, 2005) was an American mathematical scientist who made contributions to industrial engineering Industrial Engineering is an engineering profession that is concerned with the optimization ...
in 1947, solves LP problems by constructing a feasible solution at a vertex of the
polytope In elementary geometry Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, shape, size, and relativ ...
and then walking along a path on the edges of the polytope to vertices with non-decreasing values of the objective function until an optimum is reached for sure. In many practical problems, " stalling" occurs: many pivots are made with no increase in the objective function. 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
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

algorithm
is quite efficient and can be guaranteed to find the global optimum if certain precautions against ''cycling'' are taken. The simplex algorithm has been proved to solve "random" problems efficiently, i.e. in a cubic number of steps, which is similar to its behavior on practical problems. However, the simplex algorithm has poor worst-case behavior: Klee and Minty constructed a family of linear programming problems for which the simplex method takes a number of steps exponential in the problem size. In fact, for some time it was not known whether the linear programming problem was solvable in
polynomial time In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of com ...
, i.e. of complexity class P.


Criss-cross algorithm

Like the simplex algorithm of Dantzig, the
criss-cross algorithm In optimization (mathematics), mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear programming, linear i ...
is a basis-exchange algorithm that pivots between bases. However, the criss-cross algorithm need not maintain feasibility, but can pivot rather from a feasible basis to an infeasible basis. The criss-cross algorithm does not have polynomial time-complexity for linear programming. Both algorithms visit all 2''D'' corners of a (perturbed)
cube In geometry Geometry (from the grc, γεωμετρία; ' "earth", ' "measurement") is, with , one of the oldest branches of . It is concerned with properties of space that are related with distance, shape, size, and relative position ...
in dimension ''D'', the
Klee–Minty cube The Klee–Minty cube or Klee–Minty polytope (named after Victor Klee and ) is a unit cube, unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has poor worst ...
, in the
worst case In computer science, best, worst, and average cases of a given algorithm express what the Resource (computer science), resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running ...
.


Interior point

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


Ellipsoid algorithm, following Khachiyan

This is the first
worst-case In computer science, best, worst, and average cases of a given algorithm express what the Resource (computer science), resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running ...
polynomial-time In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of com ...
algorithm ever found for linear programming. To solve a problem which has ''n'' variables and can be encoded in ''L'' input bits, this algorithm runs in O(n^6 L) time.
Leonid Khachiyan Leonid Genrikhovich Khachiyan (; russian: Леонид Генрихович Хачиян; May 3, 1952April 29, 2005) was a Soviet and American mathematician and computer scientist A computer scientist is a person who has acquired the knowledg ...
solved this long-standing complexity issue in 1979 with the introduction of the
ellipsoid method In mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimiza ...
. The convergence analysis has (real-number) predecessors, notably the
iterative method Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...

iterative method
s developed by Naum Z. Shor and the
approximation algorithm In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , an ...
s by Arkadi Nemirovski and D. Yudin.


Projective algorithm of Karmarkar

Khachiyan's algorithm was of landmark importance for establishing the polynomial-time solvability of linear programs. The algorithm was not a computational break-through, as the simplex method is more efficient for all but specially constructed families of linear programs. However, Khachiyan's algorithm inspired new lines of research in linear programming. In 1984, proposed a projective method for linear programming. Karmarkar's algorithm improved on Khachiyan's worst-case polynomial bound (giving O(n^L)). Karmarkar claimed that his algorithm was much faster in practical LP than the simplex method, a claim that created great interest in interior-point methods. Since Karmarkar's discovery, many interior-point methods have been proposed and analyzed.


Vaidya's 87 algorithm

In 1987, Vaidya proposed an algorithm that runs in O(n^3) time.


Vaidya's 89 algorithm

In 1989, Vaidya developed an algorithm that runs in O(n^) time. Formally speaking, the algorithm takes O( (n+d)^ n L) arithmetic operations in the worst case, where d is the number of constraints, n is the number of variables, and L is the number of bits.


Input sparsity time algorithms

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


Current matrix multiplication time algorithm

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


Comparison of interior-point methods and simplex algorithms

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


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 Time complexity#Strongly and weakly polynomial time, strongly polynomial-time algorithm? * Does LP admit a strongly polynomial-time algorithm to find a strictly complementary solution? * Does LP admit a polynomial-time algorithm in the real number (unit cost) model of computation? This closely related set of problems has been cited by Stephen Smale as among the Smale's problems, 18 greatest unsolved problems 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 method In mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimiza ...
s and interior point method, interior-point techniques, 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. Although the Hirsch conjecture was recently disproved for higher dimensions, it still leaves the following questions open. * Are there pivot rules which lead to polynomial-time simplex variants? * Do all polytopal graphs have polynomially bounded diameter? 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 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 Graph diameter, graph-theoretical diameter of polytopal Graph (discrete mathematics), graphs. 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 edge-following 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, criss-cross pivot methods do not preserve (primal or dual) feasibilitythey 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 polytopal graphs, graphs of arrangement polytopes are known to have small diameter, allowing the possibility of strongly polynomial-time criss-cross pivot algorithm without resolving questions about the diameter of general polytopes.


Integer unknowns

If all of the unknown variables are required to be integers, then the problem is called an integer 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. 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, and in fact the decision version was one of Karp's 21 NP-complete problems. 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 because they are even more general than ILP programs. 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 or – more general – where the system has the total dual integrality (TDI) property. Advanced algorithms for solving integer linear programs include: * cutting-plane method * Branch and bound * Branch and cut * Branch and price * if the problem has some extra structure, it may be possible to apply delayed column generation. Such integer-programming algorithms are discussed by Manfred W. Padberg, 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 P = \ is said to be integral if for all bounded feasible objective functions ''c'', the linear program \ has an optimum x^* with integer coordinates. As observed by Edmonds and Giles in 1977, one can equivalently say that the polyhedron P is integral if for every bounded feasible integral objective function ''c'', the optimal ''value'' of the linear program \ is an integer. Integral linear programs are of central importance in the polyhedral aspect of combinatorial optimization 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 In mathematics, the relaxation of a Mixed integer linear programming, (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are o ...
is integral, then it is the desired description of the convex hull of feasible (integral) solutions. 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 NP-hard 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 polynomial-size 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 matrix, totally unimodular. There are other general methods including the integer decomposition property and total dual integrality. Other specific well-known integral LPs include the matching polytope, lattice polyhedra, submodular flow polyhedra, and the intersection of two generalized polymatroids/''g''-polymatroids – e.g. see Schrijver 2003.


Solvers and scripting (programming) languages

Permissive free software licence, Permissive licenses: Copyleft, Copyleft (reciprocal) licenses: MINTO (Mixed Integer Optimizer, an integer programming solver which uses branch and bound algorithm) has publicly available source code but is not open source. Proprietary software, Proprietary licenses:


See also

* Convex programming * Dynamic programming * * Input–output model * Job shop scheduling * Linear algebra * Linear production game * Linear-fractional programming (LFP) * LP-type problem * Mathematical programming * Nonlinear programming * Oriented matroid * Quadratic programming, a superset of linear programming * Semidefinite programming * Shadow price * Simplex algorithm, used to solve LP problems


Notes


References

* * F. L. Hitchcock:
The distribution of a product from several sources to numerous localities
', Journal of Mathematics and Physics, 20, 1941, 224–230. * G.B Dantzig:
Maximization of a linear function of variables subject to linear inequalities
', 1947. Published pp. 339–347 in T.C. Koopmans (ed.):''Activity Analysis of Production and Allocation'', New York-London 1951 (Wiley & Chapman-Hall) * J. E. Beasley, editor. ''Advances in Linear and Integer Programming''. Oxford Science, 1996. (Collection of surveys) * * Karl-Heinz Borgwardt, ''The Simplex Algorithm: A Probabilistic Analysis'', Algorithms and Combinatorics, Volume 1, Springer-Verlag, 1987. (Average behavior on random problems) * Richard W. Cottle, ed. ''The Basic George B. Dantzig''. Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Selected papers by George B. Dantzig) * George B. Dantzig and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag. * George B. Dantzig and Mukund N. Thapa. 2003. ''Linear Programming 2: Theory and Extensions''. Springer-Verlag. (Comprehensive, covering e.g. simplex algorithm, pivoting and interior-point algorithms, large-scale problems, Dantzig–Wolfe decomposition, decomposition following Dantzig–Wolfe and Benders' decomposition, Benders, and introducing stochastic programming.) * * * * * Evar D. Nering and Albert W. Tucker, 1993, ''Linear Programs and Related Problems'', Academic Press. (elementary) * M. Padberg, ''Linear Optimization and Extensions'', Second Edition, Springer-Verlag, 1999. (carefully written account of primal and dual simplex algorithms and projective algorithms, with an introduction to integer linear programming – featuring the traveling salesman problem for Odysseus.) * Christos H. Papadimitriou and Kenneth Steiglitz, ''Combinatorial Optimization: Algorithms and Complexity'', Corrected republication with a new preface, Dover. (computer science) * (Invited survey, from the International Symposium on Mathematical Programming.) * * (Computer science)


Further reading

* Dmitris Alevras and Manfred W. Padberg,
Linear Optimization and Extensions: Problems and Solutions
', Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.) * Chapter 4: Linear Programming: pp. 63–94. Describes a randomized half-plane intersection algorithm for linear programming. * A6: MP1: INTEGER PROGRAMMING, pg.245. (computer science, complexity theory) * (elementary introduction for mathematicians and computer scientists) * Cornelis Roos, Tamás Terlaky, Jean-Philippe Vial, ''Interior Point Methods for Linear Optimization'', Second Edition, Springer-Verlag, 2006. (Graduate level) * * Alexander Schrijver, ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, (mathematical) * * (linear optimization modeling) * H. P. Williams,
Model Building in Mathematical Programming
', Fifth Edition, 2013. (Modeling) * Stephen J. Wright, 1997,
Primal-Dual Interior-Point Methods
', SIAM. (Graduate level) * Yinyu Ye, 1997, ''Interior Point Algorithms: Theory and Analysis'', Wiley. (Advanced graduate-level) * Günter M. Ziegler, Ziegler, Günter M., Chapters 1–3 and 6–7 in ''Lectures on Polytopes'', Springer-Verlag, New York, 1994. (Geometry)


External links


Guidance On Formulating LP ProblemsMathematical Programming Glossary
{{Authority control Linear programming, Convex optimization Geometric algorithms P-complete problems