jwp@sdchema.UUCP (John Pierce) (12/07/84)
About a week ago I caught about the last minute or so of a Nat'l Public Radio
spot that said somebody (at Bell Labs?) has come up with a new alogrithm for
solving linear programming problems. I'm reasonably certain I heard them say
it was better than an order of magnitude faster than simplex, and even better
than that for large problems. Naturally, I expected to immediately see some
discussion in one of these groups (along with 6 different implementations in
net.sources). However, so far... nothing.
Does anyone have any solid information? Maybe even a pointer to a journal
article?
John Pierce, Chemistry, UC San Diego
{decvax,sdcsvax}!sdchema!jwppaver@ut-ngp.UUCP (Bob Paver) (12/10/84)
Someone had mentioned this new algorithm to me. Here's what I found out. From "OR/MS Today" (A joint publication of ORSA and TIMS), Vol 11, No. 5. Karmarkar Develops Super Fast LP Solution; Session on Method Nov. 27 at Dallas Meeting Narendra Karmarkar, a young mathematician at AT&T Bell Laboratories, has developed a new method for solving linear programming problems that promises to be much faster than the current simplex method devixed by George Dantzig forty years ago. In one test, where Karmarkar ran his program in FORTRAN (a higher level language and therefore slower) against the fastest simplex program available (in IBM assembly language) on a 5,000 variable LP problem, Karmarkar's program was 50 times faster. As LP problems become larger, Karmarkar's method becomes even more superior. This is because the simplex method is an exponential time algorithm, with the solution time increasing as an exponential function of the size of the problem. Karmarkar's method is a polynomial time algorithm where the running time is a polynomial function of the number variables in the problem. The difference between the two types of algorithms can be dramatic. For example, a polynomial time algorithm with CHI**3 (chi cubed) steps can take 1/5 of a second of computer time when CHI is 100. An exponential time algorithm with 3**CHI (3 to the CHI power) steps might require billions of centuries of computer time when CHI is 100. In the simplex approach, the computer searches from vertex to vertex of a multidimensional polytope to find the best one. In Karmarkar's approach, the computer goes into the interior and creates a sequence of spheres inside the polytope that converge on the desired vertex. Karmarkar's method works in a strange mathematical space, somewhat akin to the hyperbolic geometry of relativity theory, in which the polytope is transformed to a regular geometric figure that is the multidimensional analog of an equilateral triangle. The method has the promise of opening up whole new areas of inquiry and solving problems which previously were too large to handle. A special seminar on the method will be given by Karmarkar at the ORSA/TIMS meeting in Dallas on Tuesday, November 27, 1984 at 8 a.m. The announcement of Karmarkar's discovery came too recently to be included in the Meeting Bulletin.