PAPERBACK
\$52.75

• #### 12 Missing Pieces, Derandomization, and Concluding Remarks 175-178

LP is one of the fundamental problems in operations research and computer science. It was formulated in the 1940s by George Dantzig, who also proposed a method for solving it. Since then, the problem has been studied in thousands of scientific papers and hundreds of books, and interest in the problem has stayed on a very high level. One reason for this is the wide applicability of LP: it is used to model practical, real-life problems in economics, industry, communications, military, and numerous other areas. It is perhaps the most widely used optimization model in the world, and except data structures, perhaps the largest single use of computer resources (see Lovász, 1980.) Another reason is that LP problems with special structure arise in various theoretical and practical areas. Yet another reason is that some fundamental properties of LP and its algorithms are still not fully understood. One of these is the efficiency of the simplex method, which will be discussed here.

The method that was proposed by Dantzig for solving LP is the simplex method (e.g., Dantzig, 1963). To describe it geometrically, we need some terminology: A point in Rd is feasible if it satisfies all the constraints. The set of feasible points,

is a polyhedron, i.e., the intersection of a finite set of half-spaces. Each half-space is of the form , and its corresponding hyperplane is {x|Ai*x = bi}. (Ai*. denotes the ith row in A.) For simplicity, we assume that the problem is nondegenerate; i.e., each set of d hyperplanes meet at a distinct single point. In that case, if , the dimension of X is d, and each feasible point in which exactly d of the inequalities are satisfied as equalities is a vertex of X. Vertices are adjacent if they are connected by an edge of X, or, equivalently, if their defining sets of equalities have d-1 identical elements. It is not hard to see that if there is an optimal solution, its value will be obtained at some vertex of X. Assuming non degeneracy, the set of feasible points lying on one defining hyperplane is (if nonempty) of dimension d -1 and is called a facet of the polyhedron.

The simplex method starts from a feasible vertex, and moves in each iteration to an adjacent vertex, until eventually either an optimal vertex is reached or the algorithm recognizes at some vertex that the problem is unbounded. The move from one vertex to an adjacent one is called a pivot, and it can be realized mathematically by a simple manipulation of the constraints matrix. Usually, the next vertex is chosen so that the objective

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001