Solving Linear ProgramsGeometric InterpretationThe constraints determine the set of feasible solutions. Thisis a polyhedron, the higher dimensional generalization of a 2-dimensional polygon.Finding the maximum of a linear objective function of the formZ = cx over this polyhedron essentially means to find a vertex ofthe polyhedron that is the farthest in the direction determinedby the vector c:TTTTT¯¯¯¯¯¯¯¯¯XXXXXXXXXXAAAAA¿¿¿¿¿¿-c← OptimumIn case there are only two variables, this can be graphically represented and solved in the plane. Graphical solution: After finding the polygonal boundary of the feasible domain D, as illustrated in the figure below, we “push” the line 3x1+3x2 = a , representing the objective function, as far as possible, so that it still intersects D. The optimum will be attained at a vertex of the polygon. If, however, as typical in applications, there are many variables, this simple graphical approach does not work, one needs more systematic methods.Comments on LP AlgorithmsFinding the optimal solution in Linear Programming takes rel-atively complex algorithms. Studying the details of LP algo-rithms is beyond the scope of this course, since in most cases thenetwork designer can apply off-the-shelf commercial software. Alot of freeware is also available on the Internet.Some historical points about solving linear programs:• The first and most widely used LP algorithm has beenthe Simplex method of Dantzig, published in 1951. Thekey idea of the method is to explore the vertices of thepolyhedron, moving along edges, until an optimal vertex isreached.• There are many variants of the Simplex Method, and theyusually work fast in practice. In pathological worst cases,however, they may take exponential running time.• It was a long standing open problem whether linear pro-gramming could be solved by a polynomial-time algorithmat all, in the worst case. The two most important discov-eries in this area were the following:– The first polynomial-time LP algorithm was publishedby Khachiyan in 1979. This result was considered atheoretical breakthrough, but was not very practical.– A practically better algorithm was found by Karmarkarin 1984. This is a so called interior point method thatstarts from a point in the polyhedron and proceeds to-wards the optimum in a step-by-step descent fashion.Later many variants, improvements and implementa-tions were elaborated, and now it has similar practicalpeformance as the Simplex Method, while guaranteeingpolynomially bounded worst-case running time.• It is interesting that, after more than a half century, a ma-jor problem is still open in the world of LP algorithms:does there exist an algorithm that solves the LP, such thatthe worst-case running time is bounded by a polynomialin terms of the number of variables and constraints only,independently of how large are the numbers that occur inthem? (Counting elementary arithmetic operations as sin-gle steps.) Such an algorithm is called a strongly polynomialtime algorithm. Khachiyan’s and Karmarkar’s methods donot have this feature.• LP solvers of different sorts are available as commercialsoftware, or even as freeware. Thus, the network designertypically does not have to develop his/her own LP solver.Once a problem is formulated as a linear programming task,off-the-shelf software can readily be
View Full Document
Unlocking...