An implementation of Karmarkar's algorithm for linear programming Export

@article{citeulike:6095825, abstract = {This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0.}, author = {Adler, Ilan and Resende, Mauricio G. C. and Veiga, Geraldo and Karmarkar, Narendra}, citeulike-article-id = {6095825}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/BF01587095}, citeulike-linkout-1 = {http://www.springerlink.com/content/m570lr51712773h2}, day = {1}, doi = {10.1007/BF01587095}, journal = {Mathematical Programming}, keywords = {lp}, month = {May}, number = {1}, pages = {297--335}, posted-at = {2009-11-10 21:21:46}, priority = {2}, title = {An implementation of Karmarkar's algorithm for linear programming}, url = {http://dx.doi.org/10.1007/BF01587095}, volume = {44}, year = {1989} }

TY - JOUR ID - citeulike:6095825 L3 - citeulike-article-id:6095825 N2 - This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0. IS - 1 JF - Mathematical Programming EP - 335 TI - An implementation of Karmarkar's algorithm for linear programming VL - 44 SP - 297 KW - lp AU - Adler, Ilan AU - Resende, Mauricio AU - Veiga, Geraldo AU - Karmarkar, Narendra PY - 1989/05/01/ UR - http://dx.doi.org/10.1007/BF01587095 ER -