Commonly known as Karmarkar's algorithm, the interior-point technique is proving especially powerful for the solution of large-scale linear programming problems, with better performance bounds than the simplex algorithm. Delta Airlines, for example, uses interior-point methods to schedule its air crews and planes. A software package and user's guide is included with IBM PC implementations of the Primal, Dual, and Primal-Dual interior-point linear programming algorithms. Annotation copyright Book News, Inc. Portland, Or.
Linear programming is widely used in industry to solve complex planning and resourceallocation problems. This book provides practitioners as well as students of this generalmethodology with an easily accessible introduction to the new class of algorithms known asinterior-point methods for linear programming. In addition to presenting the theoretical andalgorithmic background necessary for dealing with specific interior-point linear programmingalgorithms, it offers a review of modeling linear programming problems, a review of the simplexalgorithm that has been used to solve linear programming problems in the past, and a complete user'sguide to the software that is included with the book.The interior-point technique is provingespecially powerful for the solution of large-scale linear programming problems, with betterperformance bounds than the simplex algorithm. For example, the U.S. Military airlift command hassolved their scheduling problem using interior-point algorithms much faster and with a longerplanning horizon than was possible with the simplex algorithms, and Delta expects to save millionsof dollars by using interior-point methods to schedule their air crews and planes.The softwarepackage is designed for use on IBM-PC microcomputers (and compatibles), a platform that provides anideal environment for students of linear programming interested in exploring and studying these newalgorithms.Contents: Preparations. Introduction. Modeling Linear Optimization Problems. The SimplexAlgorithm. A First Look at an Interior Point Algorithm. Algorithms. The Primal Algorithm. The DualAlgorithm. The Primal-Dual Algorithm. Implementation Issues. Solutions. The Integrated Environment.Command Line Operations. Appendixes.
This book provides practitioners as well as students of this general methodology withan easily accessible introduction to the new class of algorithms known as interior-point methods forlinear programming.
