A linear programming race.A linear programming race Linear programing, or "planning," problems involve things like finding the cheapest way to manufacture a product, or the shortest route for distributing goods to a dealer network, or the fastest way to link long-distance telephone calls. Such problems may include thousands of variables and constraints CONSTRAINTS - A language for solving constraints using value inference. ["CONSTRAINTS: A Language for Expressing Almost-Hierarchical Descriptions", G.J. Sussman et al, Artif Intell 14(1):1-39 (Aug 1980)]. that must be satisfied. Two years ago, Narendra Karmarkar Narendra K. Karmarkar (b. 1957) is an Indian mathematician, renowned for developing Karmarkar's algorithm. Dr. Karmarkar received his B.Tech at the IIT Bombay in 1978. Later, he received his M.S. at the California Institute of Technology, and his Ph.D. of AT&T Bell Laboratories in Murray Hill Murray Hill may refer to one of the following places:
Furthermore, competing algorithms are difficult to compare. The results depend on the nature of the problem, the type of computer and the particular version of the algorithm used. Many different implementations of the simplex method simplex method Standard technique in linear programming for solving an optimization problem, typically one involving a function and several constraints expressed as inequalities. are in use, and even for the much newer Karmarkar technique, several versions now exist. Recently, Ilan Adler and his colleagues at the University of California at Berkeley (body, education) University of California at Berkeley - (UCB) See also Berzerkley, BSD. http://berkeley.edu/. Note to British and Commonwealth readers: that's /berk'lee/, not /bark'lee/ as in British Received Pronunciation. successfully implemented the Karmarkar algorithm and tested their implementation on a set of 30 special problems. In 25 cases, the Karmarkar method found the answer faster than a version of the simplex method running on the same computer. The Karmarkar method ran significantly faster on larger problems, but even for small problems and in a few special cases, this method was only a little slower. At AT&T, the method is being tested on a practical problem that concerns overseas communications networks The transmission channels interconnecting all client and server stations as well as all supporting hardware and software. . This network planning project involves but 42,500 variables and 15,000 constraints. Results so far show that the AT&T implementation of the Karmarkar method computes the answers at least 10 times faster than a simplex software package. Writing in the current issue of AT&T's RECORD, Karmarkar and his colleagues report, "Although [the algorithm's] full capabilities and limitations are still being explored, its ability to greatly reduce computation times In computational complexity theory, computation time is a measure of how many steps are used by some abstract machine in a particular computation. For any given model of abstract machine, the computation time used by that abstract machine is a computational resource which can be for some large practical problems has already been demonstrated." However, AT&T has thus far refused to make its implementation public. |
|
||||||||||||||
Printer friendly
Cite/link
Email
Feedback
Reader Opinion