What is LP?

A linear programming (abbreviated by LP) is to find a maximizer or minimizer of a linear function subject to linear inequality constraints. More precisely,

$$\quad f(x) := \sum_{j=1}^d c_j x_j$$ maximize (12)

$$\sum_{j=1}^{d} a_{ij} x_j \le b_i i=1,2,\ldots, m,$$ subject to (13)

where $A=[a_{ij}]$ is a given rational $m \times d$ matrix, $c=[c_j]$ and $b=[b_i]$ are given rational $d$- and $n$-vector. We often write an LP in matrix form:

$$\quad f(x) := c^T x$$ maximize (14)

$$A x \le b.$$ subject to (15)

Theoretically every rational LP is solvable in polynomial time by both the ellipsoid method of Khachian (see [Kha79,Sch86]) various interior point methods (see [Kar84,RTV97]). The well-known simplex method of Dantzig (see [Dan63,Chv83]) has no known polynomial variants. In practice, very large LPs can be solved efficiently by both the simplex method and interior-point methods. For example, it is very easy on a standard unix station to solve an LP with $d=100$ and $m=100,000$, while the vertex enumeration/convex hull computation of the same size is simply intractable. There are many commercial codes and public codes available. See the LP FAQ [FG]. Two excellent books on LP are Chvatal's textbook [Chv83] and Schrijver's ``researcher's bible'' [Sch86].