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.