Karmarkars' algorithm: extensions and implementation


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.

Additional Information: Copyright © Abdellah Salhi, 1989. Abdellah Salhi asserts their moral right to be identified as the author of this thesis. This copy of the thesis has been supplied on condition that anyone who consults it is understood to recognise that its copyright rests with its author and that no quotation from the thesis and no information derived from it may be published without appropriate permission or acknowledgement. If you have discovered material in Aston Publications Explorer which is unlawful e.g. breaches copyright, (either yours or that of a third party) or any other law, including but not limited to those relating to patent, trademark, confidentiality, data protection, obscenity, defamation, libel, then please read our Takedown Policy and contact the service immediately.
Institution: Aston University
Uncontrolled Keywords: Linear Programming,Least Squares,Karmarkars' Algorithm,Duality,Partitioning
Last Modified: 08 Dec 2023 08:23
Date Deposited: 09 Dec 2010 11:13
Completed Date: 1989
Authors: Salhi, Abdellah

Export / Share Citation


Additional statistics for this record