publication . Article . Preprint . 2014

CurveLP-A MATLAB implementation of an infeasible interior-point algorithm for linear programming

Yaguang Yang;
Open Access
  • Published: 17 Jun 2014 Journal: Numerical Algorithms, volume 74, pages 967-996 (issn: 1017-1398, eissn: 1572-9265, Copyright policy)
  • Publisher: Springer Science and Business Media LLC
Abstract
Mehrotra's algorithm has been the most successful infeasible interior-point algorithm for linear programming since 1990. Most popular interior-point software packages for linear programming are based on Mehrotra's algorithm. This paper describes a proposal and implementation of an alternative algorithm, an arc-search infeasible interior-point algorithm. We will demonstrate, by testing Netlib problems and comparing the test results obtained by the arc-search infeasible interior-point algorithm and Mehrotra's algorithm, that the proposed arc-search infeasible interior-point algorithm is a more reliable and efficient algorithm than Mehrotra's algorithm.
Persistent Identifiers
Subjects
ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICS
free text keywords: Applied Mathematics, Mathematics - Optimization and Control, Simplex algorithm, Interior point method, MATLAB, computer.programming_language, computer, Netlib, Linear programming, Algorithm, Criss-cross algorithm, Mathematical optimization, Software, business.industry, business, Theory of computation, Mathematics
36 references, page 1 of 3

[1] S. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, 1997.

[2] N. Megiddo, Pathway to the optimal set in linear propramming, in Program in Mathematical Programming: interior point and related methods, N. Megiddo, ed., Springer Verlag, New York, (1989), pp. 131-158. [OpenAIRE]

[3] M. Kojima, S. Mizuno, and A. Yoshise, A polynomial-time algorithm for a class of linear complementarity problem, Mathematical Programming, 44, (1989), pp. 1-26. [OpenAIRE]

[4] M. Kojima, S. Mizuno, and A. Yoshise, A primal-dual interior point algorithm for linear programming, in Progress in Mathematical Programming: Interior-point and Related Methods, N. Megiddo, ed., Springer-Verlag, New York, 1989. [OpenAIRE]

[5] S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM Journal on Optimization, 2, (1992), pp. 575-601. [OpenAIRE]

[6] I. Lustig, R. Marsten, and D. Shannon, Computational experience with a primaldual interior-point method for linear programming, Linear Algebra and Its Applications, 152, (1991), pp. 191-222. [OpenAIRE]

[7] I. Lustig, R. Marsten, and D. Shannon, On implementing Mehrotra's predictorcorrector interior-point method for linear programming, SIAM Journal on Optimization, 2, (1992), pp. 432-449. [OpenAIRE]

[9] Y. Zhang, On the convergence of a class of infeasible-interior-point methods for the horizontal linear complementarity problem, SIAM Journal on Optimization, Vol.4, (1994), pp. 208-227.

[10] S. Mizuno, M. Todd, and Y. Ye, On adaptive step primal-dual interior-point algorithms for linear programming, Mathematics of Operations Research, 18, (1993), pp. 964-981.

[11] J. Miao, Two infeasible interior-point predictor-corrector algorithms for linear programming, SIAM Journal on Optimization, Vol. 6, (1996), pp. 587-599.

[12] C. Roos, A full-Newton step O(n) infeasible interior-point algorithm for linear optimization, SIAM Journal on Optimization, Vol. 16(4), (2006), pp. 1110-1136.

[13] M. Salahi, J. Peng, and T. Terlaky, On Mehrotra-Type Predictor-Corrector Algorithms, SIAM J. on Optimization, 18, (2007), pp. 1377-1397.

[14] B. Kheirfam, K. Ahmadi, and F. Hasani, A modified full-Newton step infeasible interior-point algoirhm for linear optimization, Asia-Pacific Journal of Operational Research, Vol. 30, (2013), pp.11-23.

[15] L. B. Winternitz A. L. Tits P.-A. Absil, Addressing Rank Degeneracy in Constraint-Reduced Interior-Point Methods for Linear Optimization, J Optim Theory Appl 160, (2014), pp. 127-157.

[16] J. Czyzyk, S. Mehrotra, M. Wagner, and S. J. Wright, PCx User Guide (version 1.1), Technical Report OTC 96/01, Optimization Technology Center, 1997.

36 references, page 1 of 3
Any information missing or wrong?Report an Issue