Linear programming

Linear programming

Overview
Linear programming is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model
Mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used not only in the natural sciences and engineering disciplines A mathematical model is a...

 for some list of requirements represented as linear relationships. Linear programming is a specific case of mathematical programming (mathematical optimization).

More formally, linear programming is a technique for the optimization of a linear
Linear
In mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...

 objective function, subject to linear equality and linear inequality
Linear inequality
In mathematics a linear inequality is an inequality which involves a linear function.-Definitions:When two expressions are connected by 'greater than' or 'less than' sign, we get an inequation....

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

.
Discussion
Ask a question about 'Linear programming'
Start a new discussion about 'Linear programming'
Answer questions from other users
Full Discussion Forum
 
Unanswered Questions
Encyclopedia
Linear programming is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model
Mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used not only in the natural sciences and engineering disciplines A mathematical model is a...

 for some list of requirements represented as linear relationships. Linear programming is a specific case of mathematical programming (mathematical optimization).

More formally, linear programming is a technique for the optimization of a linear
Linear
In mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...

 objective function, subject to linear equality and linear inequality
Linear inequality
In mathematics a linear inequality is an inequality which involves a linear function.-Definitions:When two expressions are connected by 'greater than' or 'less than' sign, we get an inequation....

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

. Its feasible region is a convex polyhedron, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

-valued affine function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such point exists.

Linear programs are problems that can be expressed in canonical form
Canonical form
Generally, in mathematics, a canonical form of an object is a standard way of presenting that object....

:
where x represents the vector of variables (to be determined), c and b are vectors
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

 of (known) coefficients and A is a (known) matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

 of coefficients. The expression to be maximized or minimized is called the objective function (cTx in this case). The equations Ax ≤ b are the constraints which specify a convex polytope
Convex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn...

 over which the objective function is to be optimized. (In this context, two vectors are comparable
Comparability
In mathematics, any two elements x and y of a set P that is partially ordered by a binary relation ≤ are comparable when either x ≤ y or y ≤ x...

 when every entry in one is less-than or equal-to the corresponding entry in the other. Otherwise, they are incomparable.)

Linear programming can be applied to various fields of study. It is used most extensively in business and economics, but can also be utilized for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment
Assignment problem
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics...

, and design.

History


The problem of solving a system of linear inequalities dates back at least as far as Fourier
Joseph Fourier
Jean Baptiste Joseph Fourier was a French mathematician and physicist best known for initiating the investigation of Fourier series and their applications to problems of heat transfer and vibrations. The Fourier transform and Fourier's Law are also named in his honour...

, after whom the method of Fourier-Motzkin elimination is named. The three founders of the subject are considered to be Leonid Kantorovich
Leonid Kantorovich
Leonid Vitaliyevich Kantorovich was a Soviet mathematician and economist, known for his theory and development of techniques for the optimal allocation of resources...

, the Russian mathematician who developed the earliest linear programming problems in 1939, George Dantzig
George Dantzig
George Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....

, who published the simplex method
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....

 in 1947, and John von Neumann
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...

, who developed the theory of the duality in the same year. The earliest linear programming was first developed by Leonid Kantorovich
Leonid Kantorovich
Leonid Vitaliyevich Kantorovich was a Soviet mathematician and economist, known for his theory and development of techniques for the optimal allocation of resources...

, a Russian mathematician, in 1939. It was used during World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...

 to plan expenditures and returns in order to reduce costs to the army and increase losses to the enemy. The method was kept secret until 1947 when George B. Dantzig
George Dantzig
George Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....

 published the simplex method
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....

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

 developed the theory of duality as a linear optimization solution, and applied it in the field of game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

. Postwar, many industries found its use in their daily planning.

The linear-programming problem was first shown to be solvable in polynomial time by Leonid Khachiyan
Leonid Khachiyan
Leonid Genrikhovich Khachiyan was a Soviet mathematician of Armenian descent who taught Computer Science at Rutgers University. He was most famous for his Ellipsoid algorithm for linear programming, which was the first such algorithm known to have a polynomial running time...

 in 1979, but a larger theoretical and practical breakthrough in the field came in 1984 when Narendra 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 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 is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...

 can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as 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 the behavior of how the individual modern household and firms make decisions to allocate limited resources. Typically, it applies to markets where goods or services are being bought and sold...

 and company management, such as planning, production, transportation, technology and other issues. Although the modern management issues are ever-changing, most companies would like to maximize profits or minimize costs with limited resources. Therefore, many issues can be characterized as linear programming problems.

Standard form


Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following four parts:
  • A linear function to be maximized
e.g.
  • Problem constraints of the following form
e.g.

  • Non-negative variables
e.g.

  • Non-negative right hand side constants


The problem is usually expressed in matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

 form, and then becomes:


Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variable
Variable (programming)
In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...

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

Example


Suppose that a farmer has a piece of farm land, say L 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 insecticide, P kilograms. Every square kilometer of wheat requires F1 kilograms of fertilizer, and P1 kilograms of insecticide, while every square kilometer of barley requires F2 kilograms of fertilizer, and P2 kilograms of insecticide. Let S1 be the selling price of wheat per square kilometer, and S2 be the price of barley. If we denote the area of land planted with wheat and barley by x1 and x2 respectively, then profit can be maximized by choosing optimal values for x1 and x2. This problem can be expressed with the following linear programming problem in the standard form:
Maximize: S1x1 + S2x2 (maximize the revenue—revenue is the "objective function")
Subject to: 0 ≤ x1 + x2 ≤ L (limit on total area)
0 ≤ F1x1 + F2x2 ≤ F (limit on fertilizer)
0 ≤ P1x1 + P2x2 ≤ P (limit on insecticide)
x1 ≥ 0, x2 ≥ 0 (cannot plant a negative area).


Which in matrix form becomes:
maximize
subject to

Augmented form (slack form)


Linear programming problems must be converted into augmented form before being solved by the simplex algorithm
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....

. This form introduces non-negative slack variable
Slack variable
In an optimization problem, a slack variable is a variable that is added to an inequality constraint to transform it to an equality. Introducing a slack variable replaces an inequality constraint with an equality constraint and a nonnegativity constraint....

s to replace inequalities with equalities in the constraints. The problem can then be written in the following block matrix
Block matrix
In the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a matrix broken into sections called blocks. Looking at it another way, the matrix is written in terms of smaller matrices. We group the rows and columns into adjacent 'bunches'. A partition is the rectangle...

 form:
Maximize Z:
x, xs ≥ 0

where xs 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: S1x1 + S2x2 (objective function)
Subject to: x1 + x2 + x3 = L (augmented constraint)
F1x1 + F2x2 + x4 = F (augmented constraint)
P1x1 + P2x2 + x5 = P (augmented constraint)
x1, x2, x3, x4, x5 ≥ 0.

where x3, x4, x5 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:

Duality



Every linear programming problem, referred to as a primal problem, can be converted into a dual problem
Dual problem
In constrained optimization, it is often possible to convert the primal problem to a dual form, which is termed a dual problem. Usually dual problem refers to the Lagrangian dual problem but other dual problems are used, for example, the Wolfe dual problem and the Fenchel dual problem...

, which provides an upper bound to the optimal value of the primal problem. In matrix form, we can express the primal problem as:
Maximize cTx subject to Ax ≤ b, x ≥ 0;
with the corresponding symmetric dual problem,
Minimize bTy subject to ATy ≥ c, y ≥ 0.


An alternative primal formulation is:
Maximize cTx subject to Ax ≤ b;
with the corresponding asymmetric dual problem,
Minimize bTy subject to ATy = c, y ≥ 0.


There are two ideas fundamental to duality theory. One is the fact that (for the symmetric dual) the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual. The weak duality theorem states that the objective function value of the dual at any feasible solution is always greater than or equal to the objective function value of the primal at any feasible solution. The strong duality theorem states that if the primal has an optimal solution, x*, then the dual also has an optimal solution, y*, such that 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 also Farkas' lemma).

Example


Revisit the above example of the farmer who may grow wheat and barley with the set provision of some L land, F fertilizer and P insecticide. Assume now that unit prices for each of these means of production (inputs) are set by a planning board. The planning board's job is to minimize the total cost of procuring the set amounts of inputs while providing the farmer with a floor on the unit price of each of his crops (outputs), S1 for wheat and S2 for barley. This corresponds to the following linear programming problem:
Minimize: LyL + FyF + PyP (minimize the total cost of the means of production as the "objective function")
Subject to: yL + F1yF + P1yP ≥ S1 (the farmer must receive no less than S1 for his wheat)
yL + F2 yF + P2yP ≥ S2 (the farmer must receive no less than S2 for his barley)
yL ≥ 0, yF ≥ 0, yP ≥ 0 (prices cannot be negative).


Which in matrix form becomes:
Minimize:
Subject to:


The primal problem deals with physical quantities. With all inputs available in limited quantities, and assuming the unit prices of all outputs is known, what quantities of outputs to produce so as to maximize total revenue? The dual problem deals with economic values. With floor guarantees on all output unit prices, and assuming the available quantity of all inputs is known, what input unit pricing scheme to set so as to minimize total expenditure?

To each variable in the primal space corresponds an inequality to satisfy in the dual space, both indexed by output type. To each inequality to satisfy in the primal space corresponds a variable in the dual space, both indexed by input type.

The coefficients that bound the inequalities in the primal space are used to compute the objective in the dual space, input quantities in this example. The coefficients used to compute the objective in the primal space bound the inequalities in the dual space, output unit prices in this example.

Both the primal and the dual problems make use of the same matrix. In the primal space, this matrix expresses the consumption of physical quantities of inputs necessary to produce set quantities of outputs. In the dual space, it expresses the creation of the economic values associated with the outputs from set input unit prices.

Since each inequality can be replaced by an equality and a slack variable, this means each primal variable corresponds to a dual slack variable, and each dual variable corresponds to a primal slack variable. This relation allows us to complementary slackness.

Another example


Sometimes, one may find it more intuitive to obtain the dual program without looking at program matrix. Consider the following linear program:
minimize
subject to ,
,
,


We have m + n conditions and all variables are non-negative. We shall define m + n dual variables: yj and si. We get:
minimize
subject to ,
,
,
,


Since this is a minimization problem, we would like to obtain a dual program that is a lower bound of the primal. In other words, we would like the sum of all right hand side of the constraints to be the maximal under the condition that for each primal variable the sum of its coefficient
Coefficient
In mathematics, a coefficient is a multiplicative factor in some term of an expression ; it is usually a number, but in any case does not involve any variables of the expression...

s do not exceed its coefficient in the linear function. For example, x1 appears in n + 1 constraints. If we sum its constraints' coefficients we get a1,1y1 + a1,2y2 + ... + a1,nyn + f1s1. This sum must be at most c1. As a result we get:
maximize
subject to ,
,
,


Note that we assume in our calculations steps that the program is in standard form. However, any linear program may be transformed to standard form and it is therefore not a limiting factor.

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: bTy,
Subject to: ATy ≥ 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
Packing problem
Packing problems are a class of optimization problems in mathematics which involve attempting to pack objects together , as densely as possible. Many of these problems can be related to real life packaging, storage and transportation issues...

, a linear program of the form:
Maximize: cTx,
Subject to: Ax ≤ 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 of a combinatorial problem and are important in the study of approximation algorithms. For example, the LP relaxations of the 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.Suppose we have a finite set S and a list of subsets of S...

, the independent set problem, and the matching problem are packing LPs. The LP relaxations of the set cover 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...

, the vertex cover problem, and the dominating set problem are also covering LPs.

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
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...

 of the graph.

Complementary slackness


It is possible to obtain an optimal solution to the dual when only an optimal solution to the primal is known using the complementary slackness theorem. The theorem states:

Suppose that x = (x1, x2, ... , xn) is primal feasible and that y = (y1, y2, ... , ym) is dual feasible. Let (w1, w2, ..., wm) denote the corresponding primal slack variables, and let (z1, z2, ... , zn) denote the corresponding dual slack variables. Then x and y are optimal for their respective problems if and only if
  • xjzj = 0, for j = 1, 2, ... , n, and
  • wiyi = 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 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").

Existence of optimal solutions


Geometrically, the linear constraints define the feasible region, which is 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...

 polyhedron
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...

. A linear function
Linear functional
In linear algebra, a linear functional or linear form is a linear map from a vector space to its field of scalars.  In Rn, if vectors are represented as column vectors, then linear functionals are represented as row vectors, and their action on vectors is given by the dot product, or the...

 is a convex function
Convex function
In mathematics, a real-valued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...

, which implies that every local minimum is a global minimum; similarly, a linear function is a concave function
Concave function
In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.-Definition:...

, which implies that every local maximum is a global maximum.

Optimal solution need not exist, for two reasons. First, if two constraints are inconsistent, then no feasible solution exists: For instance, the constraints x ≥ 2 and x ≤ 1 cannot be satisfied jointly; in this case, we say that the LP is infeasible. Second, when the polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...

 is unbounded in the direction of the gradient of the objective function (where the gradient of the objective function is the vector of the coefficients of the objective function), then no optimal value is attained.

Optimal vertices (and rays) of polyhedra


Otherwise, if a feasible solution exists and if the (linear) objective function is bounded, then the optimum value is always attained on the boundary of optimal level-set, by the maximum principle
Maximum principle
In mathematics, the maximum principle is a property of solutions to certain partial differential equations, of the elliptic and parabolic types. Roughly speaking, it says that the maximum of a function in a domain is to be found on the boundary of that domain...

 for convex function
Convex function
In mathematics, a real-valued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...

s (alternatively, by the minimum principle for concave function
Concave function
In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.-Definition:...

s): Recall that linear functions are both convex and concave. However, some problems have distinct optimal solutions: For example, the problem of finding a feasible solution to a system of linear inequalities is a linear programming problem in which the objective function is the zero function (that is, the constant function taking the value zero everywhere): For this feasibility problem with the 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
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....

 for solving linear programs.

Algorithms



Simplex algorithm of Dantzig


The simplex algorithm
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....

, developed by George Dantzig
George Dantzig
George Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....

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

In practice, the simplex algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

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

However, the simplex algorithm has poor 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, i.e. of complexity class P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...

.

Criss-cross algorithm


Like the simplex algorithm of Dantzig, the criss-cross algorithm
Criss-cross algorithm
In mathematical optimization, the criss-cross algorithm denotes a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for...

 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
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...

 for linear programming. Both algorithms visit all 2D corners of a (perturbed) cube
Unit cube
A unit cube, sometimes called a cube of side 1, is a cube whose sides are 1 unit long. The volume of a 3-dimensional unit cube is 1 cubic unit, and its total surface area is 6 square units.- Unit Hypercube :...

 in dimension D, the Klee–Minty cube
Klee–Minty cube
The Klee–Minty cube is a unit cube whose corners have been slightly perturbed. Klee and Minty demonstrated that Dantzig's simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube".In particular, many optimization algorithms for linear optimization...

 (after Victor Klee
Victor Klee
Victor L. Klee, Jr. was a mathematician specialising in convex sets, functional analysis, analysis of algorithms, optimization, and combinatorics. He spent almost his entire career at the University of Washington in Seattle.Born in San Francisco, Vic Klee earned his B.A...

 and George J. Minty), in the worst case.

Ellipsoid algorithm, following Khachiyan


This is the first 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(n4L) pseudo-arithmetic operations on numbers with O(L) digits. Khachiyan's algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 and his long standing issue was resolved by Leonid Khachiyan
Leonid Khachiyan
Leonid Genrikhovich Khachiyan was a Soviet mathematician of Armenian descent who taught Computer Science at Rutgers University. He was most famous for his Ellipsoid algorithm for linear programming, which was the first such algorithm known to have a polynomial running time...

 in 1979 with the introduction of the ellipsoid method
Ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm, which finds an optimal solution in a finite number of steps.The...

. The convergence analysis have (real-number) predecessors, notably the iterative method
Iterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...

s developed by Naum Z. Shor
Naum Z. Shor
Naum Zuselevich Shor was a Soviet and Ukrainian Jewish 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...

 and the approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...

s by Arkadi Nemirovski and D. Yudin.

Projective algorithm of Karmarkar


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

However, Khachiyan's algorithm inspired new lines of research in linear programming. In 1984, N. Karmarkar
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 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...

 improved on Khachiyan's worst-case polynomial bound (giving ). Karmarkar claimed that his algorithm was much faster in practical LP than the simplex method, a claim that created great interest in interior-point methods. Its projective geometry is interesting.

Path-following algorithms


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. 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 purposes, 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 have been the most popular since the 1990s.

Comparison of interior-point methods versus simplex algorithms


The current opinion is that the efficiency 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).

LP solvers are in widespread use for optimization of various problems in industry, such as optimization of flow in transportation networks.

Open problems and recent work



There are several open problems in the theory of linear programming, the solution of which would represent fundamental breakthroughs in mathematics and potentially major advances in our ability to solve 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
Steven Smale a.k.a. Steve Smale, Stephen Smale is an American mathematician from Flint, Michigan. He was awarded the Fields Medal in 1966, and spent more than three decades on the mathematics faculty of the University of California, Berkeley .-Education and career:He entered the University of...

 as among the 18 greatest unsolved problems
Smale's problems
Smale's problems refers to a list of eighteen unsolved problems in mathematics that was proposed by Steve Smale in 2000. Smale composed this list in reply to a request from Vladimir Arnold, then president of the International Mathematical Union, who asked several mathematicians to propose a list of...

 of the 21st century. In Smale's words, the third version of the problem "is the main unsolved problem of linear programming theory." While algorithms exist to solve linear programming in weakly polynomial time, such as the ellipsoid method
Ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm, which finds an optimal solution in a finite number of steps.The...

s and interior-point techniques
Interior point method
Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems.The interior point method was invented by John von Neumann...

, no algorithms have yet been found that allow strongly 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
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. That is, any two vertices of the polytope must be connected to each other by a...

 was recently disproved for higher dimensions, it still leaves the following questions open.
  • Are there pivot rules which lead to 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-theoretical diameter of polytopal graphs
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...

. 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) 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 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 the unknown variables are all required to be integers, then the problem is called an integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...

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

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
    Branch and price
    In applied mathematics, branch and price is a method of combinatorial optimization for solving integer linear programs,...

  • if the problem has some extra structure, it may be possible to apply delayed column 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...

    .

Such integer-programming algorithms are discussed by Padberg and in Beasley.

Integral linear programs


A linear program in real variables is said to be integral if it has at least one optimal solution which is integral. Likewise, a polyhedron is said to be integral if for all bounded feasible objective functions c, the linear program has an optimum with integer coordinates. As observed by Edmonds and Giles in 1977, one can equivalently say that a polyhedron is integral if for every bounded feasible integral objective function c, the optimal value of the linear progam is an integer.

Integral linear programs are of central importance in the polyhedral aspect of combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...

 since they provide an alternate characterization of a problem. Specifically, for any problem, the convex hull of the solutions is an integral polyhedron; if this polyhedron has a nice/compact description, then we can efficiently find the optimal feasible solution under any linear objective. Conversely, if we can prove that a linear programming relaxation is integral, then it is the desired description of the convex hull of feasible (integral) solutions.

Note that terminology is not consistent throughout the literature, so one should be careful to distinguish the following two concepts,
  • in an integer linear program, described in the previous section, variables are forcibly constrained to be integers, and this problem is 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. 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 2 generalized polymatroids/g-polymatroids --- e.g. see Schrijver 2003.

A bounded integral polyhedron is sometimes called a convex lattice polytope
Convex lattice polytope
A convex lattice polytope is a geometric object playing an important role in discrete geometry and combinatorial commutative algebra. It is a polytope in a Euclidean space Rn which is a convex hull of finitely many points in the integer lattice Zn ⊂ Rn...

, particularly in two dimensions.

Solvers and scripting (programming) languages


Free open-source permissive
Permissive free software licence
A permissive free software licence is a class of free software licence with minimal requirements about how the software can be redistributed. This is in contrast to copyleft licences, which have reciprocity / share-alike requirements. Both sets of free software licences offer the same freedoms in...

 licenses:
Name License Brief info
OpenOpt
OpenOpt
OpenOpt is an open-source framework for numerical optimization, nonlinear equations and systems of them. It is licensed under the BSD license, making it available to be used in both open- and closed-code software. The package already has some essential ....

BSD
BSD licenses
BSD licenses are a family of permissive free software licenses. The original license was used for the Berkeley Software Distribution , a Unix-like operating system after which it is named....

Universal cross-platform numerical optimization framework,
see its LP page and other problems involved
pulp-or BSD Python module for modeling and solving linear programming problems
Pyomo BSD Python module for formulating linear programming problems with abstract models


Free open-source copyleft (reciprocal)
Copyleft
Copyleft is a play on the word copyright to describe the practice of using copyright law to offer the right to distribute copies and modified versions of a work and requiring that the same rights be preserved in modified versions of the work...

 licenses:
Name License Brief info
LP_Solve LGPL User-friendly linear and integer programming solver. Also provides DLL for program integration, and is compatible with GNU MathProg and Zimpl modelling languages.
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
Blas is mainly a Spanish given name and surname, related to Blaise. It may refer to-Places:*Piz Blas, mountain in Switzerland*San Blas , many places - see separate article, also**Cape San Blas Light, lighthouse...

, LAPACK
LAPACK
-External links:* : a modern replacement for PLAPACK and ScaLAPACK* on Netlib.org* * * : a modern replacement for LAPACK that is MultiGPU ready* on Sourceforge.net* * optimized LAPACK for Solaris OS on SPARC/x86/x64 and Linux* * *...

, 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. Uses GNU MathProg modelling language.
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
CBC 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....

a MIP solver from COIN-OR
COIN-OR
COIN-OR, which stands for Computational Infrastructure for Operations Research, is a project that aims to "create for mathematical software what the open literature is for mathematical theory." The open literature provides the OR community with a peer-review process and an archive...

CLP CPL an LP solver from COIN-OR
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 alpha release, as of 2009
SDPT3 GPL MATLAB based convex optimization solver
SeDuMi GPL MATLAB based convex optimization solver


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

 (Mixed Integer Optimizer, an integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...

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

Proprietary:
Proprietary software
Proprietary software is computer software licensed under exclusive legal right of the copyright holder. The licensee is given the right to use the software under certain conditions, while restricted from other uses, such as modification, further distribution, or reverse engineering.Complementary...

Name Brief info
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. APMonitor is suited for large-scale problems and allows solutions of dynamic...

AIMMS
AIMMS
AIMMS is a software system designed for modeling and solving large-scale optimization and scheduling-type problems....

AMPL
AMPL
AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and solving high-complexity problems for large-scale mathematical computation AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and...

A popular modeling language for large-scale linear, mixed integer and nonlinear optimisation with a free student version available.
Analytica Optimization modeling software that incorporates state-of-the-art algorithms for linear and nonlinear optimization. Supports LP, NLP, QP, continuous and integer optimization.
CPLEX
CPLEX
IBM ILOG CPLEX Optimization Studio is an optimization software package. In 2004, the work on CPLEX earned the first ....

Popular solver with an API for several programming languages, and also has a modelling language and works with AIMMS, AMPL, GAMS
General Algebraic Modeling System
The General Algebraic Modeling System is a high-level modeling system for mathematical optimization. GAMS is designed for modeling and solving linear, nonlinear, and mixed-integer optimization problems. The system is tailored for complex, large-scale modeling applications and allows the user to...

, MPL, OpenOpt, OPL Development Studio, and 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...

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 crossover thrash/punk band from Venice, California...

 Solver Function
FinMath A .NET
.NET Framework
The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...

 numerical library containing an interior-point primal-dual
Interior point method
Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems.The interior point method was invented by John von Neumann...

 solver.
FortMP
FortMP
FortMP is a software package for solving large-scale optimization problems. It solves linear programming problems, quadratic programming problems and mixed integer programming problems...

GAMS
General Algebraic Modeling System
The General Algebraic Modeling System is a high-level modeling system for mathematical optimization. GAMS is designed for modeling and solving linear, nonlinear, and mixed-integer optimization problems. The system is tailored for complex, large-scale modeling applications and allows the user to...

GIPALS The maximum number of constraints and variables is unlimited. The linear program solver is based on Interior-Point method (Mehrotra predictor-corrector algorithm) and optimized for large sparse linear programs by implementing the state-of-art algorithm to order the constraints matrix. The user can specify the linear program using a set of exported DLL functions.
Gurobi
Gurobi
Gurobi is a commercial software package for solving large-scale linear optimization, quadratic optimization, and mixed-integer optimization problems...

Solver with parallel algorithms for large-scale linear programs, quadratic programs and mixed-integer programs. Free for academic use.
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...

Collections of math and statistical algorithms available in C/C++, Fortran, Java and C#/.NET. Optimization routines in the IMSL Libraries include unconstrained, linearly and nonlinearly constrained minimizations, and linear programming algorithms.
Lingo
LPL
LiPS (freeware) Linear Program Solver (LiPS) is intended for solving linear programming problems. Main features: easy to use graphical interface, sensitivity analysis, goal and mixed integer programming solver. LiPS supports MPS
MPS (format)
MPS is a file format for presenting and archiving linear programming and mixed integer programming problems.- Overview :...

 and simple LP format (like lpsolve).
MATLAB
MATLAB
MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...

A general-purpose and matrix-oriented programming-language for numerical computing. Linear programming in MATLAB requires 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 programming-language for mathematics, including symbolic and numerical capabilities.
MOPS
MOSEK
MOSEK
MOSEK is a software package for the solution of linear, mixed-integer linear, quadratic, mixed-integer quadratic, quadratically constraint, conic and convex nonlinear mathematical optimization problems. The emphasize in MOSEK is on solving large scale sparse problems. Particularly the...

A solver for large scale optimization with API for several languages (C++,java,.net, Matlab and python).
NMath Stats
NMath Stats
NMath Stats is a statistical package for the Microsoft .NET Framework. It is developed by CenterSpace Software. Version 1.0 was released in December, 2003. The current version of NMath Stats is 3.2, released in July, 2010...

A general-purpose .NET
.NET Framework
The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...

 statistical library containing a simplex solver.
OptimJ
OptimJ
OptimJ is an extension of the Java with language support for writing optimization models and abstractions for bulk data processing. OptimJ aims at providing a clear and concise algebraic notation for optimization modeling, removing compatibility barriers between optimization modeling and...

A Java-based modeling language for optimization with a free version available.
SAS
SAS System
SAS is an integrated system of software products provided by SAS Institute Inc. that enables programmers to perform:* retrieval, management, and mining* report writing and graphics* statistical analysis...

/OR
A suite of solvers for Linear, Integer, Nonlinear, Derivative-Free, Network, Combinatorial and Constraint Optimization; the Algebraic modeling language
Algebraic modeling language
Algebraic Modeling Languages are high-level computer programming languages for describing and solving high complexity problems for large scale mathematical computation...

 OPTMODEL; and a variety of vertical solutions aimed at specific problems/markets, all of which are fully integrated with the SAS System
SAS System
SAS is an integrated system of software products provided by SAS Institute Inc. that enables programmers to perform:* retrieval, management, and mining* report writing and graphics* statistical analysis...

.
SCIP
SCIP (optimization software)
SCIP is a mixed integer programming solver and a framework for Branch and cut and Branch and price, developed at Zuse Institute Berlin....

A general-purpose constraint integer programming solver with an emphasis on MIP. Compatible with Zimpl modelling language. Free for academic use and available in source code.
Solver Foundation A .NET platform for modeling, scheduling, and optimization.
SoPlex The Sequential object-oriented simPlex: a general-purpose LP solver. Free for academic use and available in source code.
SuanShu A Java-based math library that supports linear programming and other kinds of numerical optimization.
TOMLAB
VisSim
VisSim
VisSim is a visual block diagram language for simulation of dynamical systems and model based design of embedded systems. It is developed by Visual Solutions of Westford, Massachusetts....

A visual block diagram
Block diagram
Block diagram is a diagram of a system, in which the principal parts or functions are represented by blocks connected by lines, that show the relationships of the blocks....

 language for simulation of dynamical system
Dynamical system
A dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...

s.
Xpress

See also

  • Mathematical programming
    Mathematical Programming
    Mathematical Programming, established in 1971, and published by Springer Science+Business Media, is the official scientific journal of the Mathematical Optimization Society. It currently consists of two series: A and B. The "A" series contains general publications. The "B" series focuses on topical...

  • Nonlinear programming
    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...

  • Convex programming
  • Dynamic programming
    Dynamic programming
    In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...

  • Simplex algorithm
    Simplex algorithm
    In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....

    , used to solve LP problems
  • Quadratic programming
    Quadratic programming
    Quadratic programming is a special type of mathematical optimization problem. It is the problem of optimizing a quadratic function of several variables subject to linear constraints on these variables....

    , a superset of linear programming
  • Shadow price
    Shadow price
    In constrained optimization in economics, the shadow price is the instantaneous change per unit of the constraint in the objective value of the optimal solution of an optimization problem obtained by relaxing the constraint...

  • MPS file format
    MPS (format)
    MPS is a file format for presenting and archiving linear programming and mixed integer programming problems.- Overview :...

  • nl file format
    Nl (format)
    nl is a file format for presenting and archiving mathematical programming problems. It supports linear and nonlinear optimization problems as well as complementarity problems , in discrete or continuous variables...

  • MIP example, job shop problem
    Job-shop problem
    The job-shop problem is a problem in discrete or combinatorial optimization, and is a generalization of the famous travelling salesman problem...


  • Linear-fractional programming (LFP)
  • Oriented matroid
    Oriented matroid
    An oriented matroid is a mathematical structure that abstracts the properties of directed graphs and of arrangements of vectors in a vector space over an ordered field...


Further reading


A reader may consider beginning with Nering and Tucker, with the first volume of Dantzig and Thapa, or with Williams.
  • Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Extensions, Universitext, 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)
  • Bernd Gärtner, Jiří Matoušek
    Jirí Matoušek (mathematician)
    Jiří Matoušek is a Czech mathematician working in computational geometry. He is a professor at Charles University in Prague and is the author of several textbooks and research monographs....

     (2006). Understanding and Using Linear Programming, Berlin: Springer. ISBN 3-540-30697-8 (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, ISBN 0-471-98232-6 (mathematical)
  • Robert J. Vanderbei
    Robert J. Vanderbei
    Robert J. Vanderbei is an American mathematician and Professor in the Department of Operations Research and Financial Engineering at Princeton University.-Biography:...

    , Linear Programming: Foundations and Extensions, 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. ISBN 978-0-387-74387-5. (An on-line second edition was formerly available. Vanderbei's site still contains extensive materials.)
  • H. P. Williams, Model Building in Mathematical Programming, Third revised Edition, 1990. (Modeling)
  • Stephen J. Wright, 1997, Primal-Dual Interior-Point Methods, SIAM. (Graduate level)
  • Yinyu Ye
    Yinyu Ye
    In mathematical optimization, Yinyu Ye is a specialist in interior point methods, especially convex minimization and in linear programming. Ye is a professor of management science at Stanford University.-Research publications:...

    , 1997, Interior Point Algorithms: Theory and Analysis, Wiley. (Advanced graduate-level)
  • Ziegler, Günter M.
    Günter M. Ziegler
    Günter M. Ziegler is a German mathematician. Ziegler is known for his research in discrete mathematics and geometry, and particularly on the combinatorics of polytopes.- Biography :...

    , Chapters 1–3 and 6–7 in Lectures on Polytopes, Springer-Verlag, New York, 1994. (Geometry)

External links