Commentary—Theory and Practice for Interior-Point Methods

The last decade has been a fascinating time for researchers interested in linear programming and its extensions. It opened with Narendra Karmarkar's theoretical paper on the computational complexity of linear programming problems and his claims that his method solved problems 50 times faster than the simplex method. After 10 years of development in both interior-point and simplex methods, we are now at a point at which both approaches can handle problems that seemed intractable before, but where interior-point methods seem to be superior to simplex algorithms for many very large-scale sparse linear programming problems. Lustig, Marsten, and Shanno (LMS) provide an excellent overview of these advances, particularly with respect to their computational significance. Of course, they have been major contributors to the development of interior-point algorithms as well as of sophisticated implementations with their OB1 code. Their experience leads to many interesting insights and also raises some questions: why ...