Linear programming

optimization problems in which the objective function and the constraints are all linear. Linear programming is the process of solving LP problems.

Linear programming is an important field of optimization for several reasons. LP problems are the easiest kind of optimization problems, since everything is linear. Furthermore, many practical problems in operations research can be expressed as linear programming problems. Finally, many algorithms for other optimization problems work by solving LP problems.

Example

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

<math> \mbox{maximize } S_1 x_1 + S_2 x_2 <math>		(maximize the profit)
<math> \mbox{subject to} <math>	<math> x_1 + x_2 \le A <math>	(limit on total acrage)
	<math> F_1 x_1 + F_2 x_2 \le F <math>	(limit on fertilizer)
	<math> P_1 x_1 + P_2 x_2 \le P <math>	(limit on insecticide)
	<math> x_1 \ge 0,\, x_2 \ge 0 <math>	(cannot plant a negative number of acres)

Theory

Geometrically, the linear constraints form a convex polytope. Since the objective function is also linear, all local optima are automatically global optima.

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

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

Barring these two pathological conditions (which are often ruled out by resource constraints integral to the problem being represented, as above), the optimum is always attained at a vertex of the polytope. However, the optimum is not necessary unique: it is possible to have a set of optimal solutions covering an edge or face of the polytope, or even the entire polytope.

Algorithms

The simplex algorithm solves LP problems by constructing an admissible solution at a vertex of the polytope, and then walking along edges of the polytope to vertices with successively higher values of the objective function until the optimum is reached. Although this algorithm is quite efficient in practice, and is guaranteed to find the global optimum, it has poor worst-case behavior: it is possible to construct a linear programming problem for which the simplex method takes a number of steps exponential in the problem size. In fact for some time it was not known whether the linear programming problem was NP-complete or polynomial-time solvable.

The first worst-case polynomial-time algorithm for the linear programming problem was proposed by Leonid Khachiyan in 1979. It was based on the ellipsoid method in nonlinear optimization by Naum Shor, which is the generalization of the ellipsoid method in convex optimization by Arkadi Nemirovski, a 2003 John von Neumann Theory Prize winner, and interior point methods. In contrasts with the simplex algorithm, which only considers point on the boundary of the polytope defined by the constraints, interior point methods move through the interior of the polytope.

In 1984, Mehrotra predictor-corrector method, which performs very well in practice even though little is known about it theoretically.

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

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

Integer unknowns

If the unknown variables are all required to be integers, then the problem is called integer programming (IP) or integer linear programming (ILP). In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in the worst case undecidable, and in many practical situations (those with bounded variables) NP-hard. 0-1 integer programming is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). It is also NP-hard.

If only some of the unknown variables are required to be integers, then the problem is called mixed integer programming (MIP). 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 integer.

An advanced algorithm for solving large integer linear programs is Delayed Column Generation