Karmarkars' algorithm: extensions and implementation

Abstract

Linear Programming (LP) is a powerful decision making tool, extensively used in various economic activities. Its success is mainly due to the efficiency of the simplex method. In recent years, however, new techniques have emerged. The present work is concerned with investigating one such technique, namely Karmarkar's algorithm and its variants, extending it to structured linear programming problems and efficiently implementing it, taking account of sparsity. A review of recent work on the algorithm and early polynomial time methods for LP such as the ellipsoid and the simplicial algorithms is presented. The performance of the simplex method is also discussed. One of the major developments in Karmarkar's algorithm is the discovery of dual variants. Duality allows the method to be simply extended to problems having an unknown optimum objective value and also to investigate postoptimality analysis. The study showed that postoptimality analysis is possible with Karmarkar's algorithm in the three cases considered (cost, right-hand side and rim). Based on Ye and Kojima's dual variant, a specialized form of the algorithm for structured LP is presented together with computational results on various problems. The results show that inherent parallelism of some linear programming problems can be efficiently exploited with Karmarkar type algorithms. The advantages of decomposition are also discussed in a wider context (eg. lack of favourable structure). Finally, an efficient implementation of a variant of the Karmarkar algorithm, which combines sparsity-preserving techniques for least squares, such as the nested dissection ordering algorithm and updating techniques is described. The performance of this implementation on realistic LP problems is reported.