Linear programming

Linear Programming is the process of solving a system of linear equalities and linear inequalities over a set of unknown real variables, along with a linear objective function to be maximized.

Many practical problems in operations research can be expressed as linear programming problems. For instance, if x1 is the number of acres planted with wheat and x2 is the number planted with corn, and a farmer has a limited number of acres A, and 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 (F1, F2, P1, P2) for wheat and corn respectively, and knows the selling price of wheat S1 and the selling price of corn S2, then the optimal number of acres to plant with wheat vs corn can be expressed as a linear program:

Subject to the linear constraints:

 x1 >= 0            (cannot plant a negative number of acres)
 x2 >= 0
 x1+x2 <= A         (limit on total acrage)
 F1*x1+F2*x2 <= F   (limit on fertilizer)
 P1*x1+P2*x2 <= P   (limit on insecticide)

maximize the objective:

 S1*x1+S2*x2

Due to the geometry of these kinds of linear constraints and the linear objective function, LP problems are "convex", which means that there are no local optima (aside from the global optimum). Furthermore, in LP the solution must be at a vertex of the n-dimensional polytope defined by the constraints. There are two situations in which no optimal solution can be found. First, if that polytope is empty (due to the constraints not being mutually satisfiable, such as x>=2, x<=1) then there can be no optimal solution, since there are no solutions at all. Alternatively, the polytope can be unbounded in the direction of the objective function (such as x1>=0, x2>=0, x1+x2>=10, objective function x1+3*x2), 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) it is possible to have either a point optimal solution, at a vertex of the polytope of admissible values, or a set of optimal solutions covering an edge or face of that polytope.

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.

More recently "interior point" algorithms have been developed which can solve a linear programming problem in polynomial worst-case time.

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.

If the unknown variables are all required to be integers, then the problem is called "integer programming". 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 (bounded variables) NP-hard.