# 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.

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.

Printer friendly Cite/link Email Feedback | |

Publication: | Science News |
---|---|

Date: | Jun 14, 1986 |

Words: | 359 |

Previous Article: | An interferon gets FDA nod. |

Next Article: | Stay tuned for Embolism Bowl. |

Topics: |