next up previous contents
Next: Polyhedral Computation Codes Up: Linear Programming Previous: Linear Programming   Contents


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,

  maximize $\displaystyle \quad f(x) :=$ $\displaystyle \sum_{j=1}^d c_j x_j$ (12)
  subject to   $\displaystyle \sum_{j=1}^{d} a_{ij} x_j \le b_i$    for all $\displaystyle i=1,2,\ldots, m,$ (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:

  maximize $\displaystyle \quad f(x) :=$ $\displaystyle c^T x$ (14)
  subject to   $\displaystyle A x \le b.$ (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].


next up previous contents
Next: Polyhedral Computation Codes Up: Linear Programming Previous: Linear Programming   Contents
Komei Fukuda 2004-08-26