Linear programming

Defines linear programming.

Linear programming is an important tool for combinatorial search problems, not only because it solves efficiently a large class of important problems, but also because it is the basic block of some fundamental techniques in this area.

A linear program consists of minimizing a linear objective function subject to a set of linear constraints over real variables constrained to be nonnegative or, in symbols,


Note first that considering only equations, nonnegative variables, and minimization is not restrictive. An inequality t 0 can be recast as an equation t - s = 0 by adding a new variable, an arbitrary variable can be expressed as the difference of two nonnegative variables, and maximization can be expressed by negating the objective function. In addition, decision problems (i.e., finding if a set of constraints is satisfiable) can be recast by adding a variable per constraint and minimizing their sum. The problem is satisfiable if and only if the optimum is zero. Note also that linear programs can be solved in polynomial time and robust solvers are now available that solve large scale linear programs. The success of linear programming led many researchers to investigate some of its generalizations.