Printer Friendly

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 that must be satisfied.

Two years ago, Narendra Karmarkar of AT&T Bell Laboratories in Murray Hill, N.J., invented a new mathematical technique that seemed to solve such problems much more quickly than a widely used technique known as the "simplex" method (SN: 12/22 & 29/84, p. 408). However, because details of how Karnarkar implemented his algorithm as a computer program were not released, no one could easily check his results.

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 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 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. 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 for some large practical problems has already been demonstrated." However, AT&T has thus far refused to make its implementation public.
COPYRIGHT 1986 Science Service, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1986, Gale Group. All rights reserved. Gale Group is a Thomson Corporation Company.

Article Details
Printer friendly Cite/link Email Feedback
Publication:Science News
Date:Jun 14, 1986
Previous Article:An interferon gets FDA nod.
Next Article:Stay tuned for Embolism Bowl.

Related Articles
Back off veto threat.
Electronics recycling bill advances.
Cynthia Knight joins South Lane.
3 incumbents retain seats on school boards.
Incumbent Hall, newcomer McCown capture LCC seats.
As they see it.
Cell of Cells: The Global Race to Capture and Control the Stem Cell.
Washington outlook.

Terms of use | Copyright © 2017 Farlex, Inc. | Feedback | For webmasters