IITBHF and IITBAA (http://www.iitbombay.org)

Flashback ...

An Interior Point Method for Linear Programming

In 1984, Narendra Karmarkar (BTech EE '78 ) made a groundbreaking discovery in the field of Linear Programming while working at the famed Bell Labs in New Jersey. The Association for Computing Machinery (ACM) awarded him the prestigious Paris Kanellakis Award for his work, and the award citation reads as follows:

"For his theoretical work in devising an Interior Point method for linear programming that provably runs in polynomial time, and for his implementation work suggesting that Interior Point methods could be effective for linear programming in practice as well as theory. Together, these contributions inspired a renaissance in the theory and practice of linear programming, leading to orders of magnitude improvement in the effectiveness of widely-used commercial optimization codes."

Linear Programming is a specific class of mathematical problems, in which a linear function is maximized (or minimized) subject to given linear constraints. This problem class is broad enough to encompass many interesting and important applications, yet specific enough to be tractable even if the number of variables is large.

A brief history of Linear Programming ... it was developed as a discipline in the 1940's, motivated initially by the need to solve complex planning problems in wartime operations. Its development accelerated rapidly in the postwar period as many industries found valuable uses for linear programming. The founders of the subject are generally regarded as George B. Dantzig, who devised the simplex method in 1947, and John von Neumann, who established the theory of duality that same year. The Nobel prize in econonmics was awarded in 1975 to the mathematician Leonid Kantorovich (USSR) and the economist Tjalling Koopmans (USA) for their contributions to the theory of optimal allocation of resources, in which linear programming played a key role. Many industries use linear programming as a standard tool, e.g. to allocate a finite set of resources in an optimal way. Examples of important application areas include airline crew scheduling, shipping or telecommunication networks, oil refining and blending, and stock and bond portfolio selection.

The simplex method has been the standard technique for solving a linear program since the 1940's. In brief, the simplex method passes from vertex to vertex on the boundary of the feasible polyhedron, repeatedly increasing the objective function until either an optimal solution is found, or it is established that no solution exists. In principle, the time required might be an exponential function of the number of variables, and this can happen in some contrived cases. In practice, however, the method is highly efficient, typically requiring a number of steps which is just a small multiple of the number of variables. Linear programs in thousands or even millions of variables are routinely solved using the simplex method on modern computers. Efficient, highly sophisticated implementations are available in the form of computer software packages.

In 1979, Leonid Khaciyan presented the ellipsoid method, guaranteed to solve any linear program in a number of steps which is a polynomial function of the amount of data defining the linear program. Consequently, the ellipsoid method is faster than the simplex method in contrived cases where the simplex method performs poorly. In practice, however, the simplex method is far superior to the ellipsoid method.

In 1984, Narendra Karmarkar introduced an interior-point method for linear programming, combining the desirable theoretical properties of the ellipsoid method and practical advantages of the simplex method. Its success initiated an explosion in the development of interior-point methods. These do not pass from vertex to vertex, but pass only through the interior of the feasible region. Though this property is easy to state, the analysis of interior-point methods is a subtle subject which is much less easily understood than the behavior of the simplex method. Interior-point methods are now generally considered competitive with the simplex method in most, though not all, applications, and sophisticated software packages implementing them are now available. Whether they will ultimately replace the simplex method in industrial applications is not clear.

A Karmarkar blog ...

Lucent - 1980s
... 1984: Karmarkar algorithm Developed by mathematician Narendra Karmarkar, this revolutionary
"linear programming" algorithm enables computers to economically ...
http://www.lucent.com/minds/discoveries/tline80b.html

ACM: Paris Kanellakis Award / Interior Point
... Narendra Karmarkar Citation For his theoretical work in devising an Interior Point
method for linear programming that provably runs in polynomial time, and for ...
http://www.acm.org/awards/pk_citations/2000.html

JOC Back Issues: Volume 1 (1989)
... a Primal-Dual Interior Method for Linear ... David Shanno. Data Structures and Programming ... for the Implementation of Karmarkar's algorithm for linear programming ...
http://joc.pubs.informs.org/BackIssues/Vol001/Vol001No02Paper03.pdf

Please review the Terms of Usage provided on the disclaimer page prior to accessing this website.
ACCESSING THIS WEBSITE SIGNIFIES YOUR AGREEMENT TO THE TERMS OF USAGE.