ArcLP: A Matlab Implementation of an 𝒪(√nL) Arc-search Infeasible Interior-Point Algorithm for Linear Programming

Yaguang Yang

doi:10.5334/jors.674

ArcLP: A Matlab Implementation of an 𝒪(√nL) Arc-search Infeasible Interior-Point Algorithm for Linear Programming

Journal of Open Research Software

Volume 14 (2026): Issue 1

By: Yaguang Yang

Open Access

|Aug 2026

Abstract

This paper presents a Matlab implementation of an arc-search infeasible interior-point algorithm for linear programming (LP), which has a proven polynomial bound of 𝒪(√nL), the best among all interior-point algorithms for LP. Software architecture and major functions are discussed. Its ease of use is described by a simple example. Crucial strategies are summarized. Quality of the software is assured because this software has been extensively tested on both PC and Linux for the widely used Netlib benchmark linear programming problems in standard form. Some benchmark test problems involve tens of thousands of constraints and hundreds of thousands of variables. For all tested problems, the code found the optimal solution. The numerical results have been compared to those obtained by the popular Mehrotra’s predictor-corrector algorithm. We conclude that the implemented algorithm not only has the best polynomial bound but also is computationally competitive compared against the popular Mehrotra’s predictor-corrector algorithm.

References

Dantzig GB. Programming in a linear structure. Econometrica. 1949;17:200–211. DOI: 10.2307/1905523
Open DOI Search in Google Scholar Back to article
Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorics. 1984;4:373–395. DOI: 10.1007/BF02579150
Open DOI Search in Google Scholar Back to article
Paparrizos K, Samaras N, Zissopoulos D. Linear Programming: Klee-Minty Examples. In: Floudas C, Pardalos P, editors. Encyclopedia of Optimization. Boston, MA: Springer; 2008. DOI: 10.1007/978-0-387-74759-0_339
Open DOI Search in Google Scholar Back to article
Mehrotra S. On the implementation of a primal-dual interior point method. SIAM Journal on Optimization. 1992;2:575–601. DOI: 10.1137/0802028
Open DOI Search in Google Scholar Back to article
Lustig IJ, Marsten RE, Shanno DF. On implementing Mehrotra’s predictor-corrector interior point method for linear programming. SIAM J. Optimization. 1992;2:435–449. DOI: 10.1137/0802022
Open DOI Search in Google Scholar Back to article
Yang Y. Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming. Numerical Algorithms. 2018;79:957–992. DOI: 10.1007/s11075-018-0469-3
Open DOI Search in Google Scholar Back to article
Todd MJ. The many facets of linear programming. Mathematical Programming, Ser. B. 2002;91:417–436. DOI: 10.1007/s101070100261
Open DOI Search in Google Scholar Back to article
Wright S. Primal-dual interior-point methods. SIAM. 1995.
Search in Google Scholar Back to article
Czyzyk J, Mehrotra S, Wagner M, Wright SJ. PCx User Guide (version 1.1). Technical Report OTC 96/01, Optimization Technology Center. 1997. DOI: 10.2172/475586
Open DOI Search in Google Scholar Back to article
Nickel S, Steinhardt C, Schlenker H, Burkart W. Decision optimization with IBM ILOG CPLEX optimization studio: A hands-on introduction to modeling with the optimization programming language (OPL). Springer Nature; 2022. DOI: 10.1007/978-3-662-65481-1
Open DOI Search in Google Scholar Back to article
Mathworks. Optimization Toolbox: User’s Guide. 2019.
Search in Google Scholar Back to article
Zhang Y. Solving large-scale linear programs by interior-point methods under the Matlab environment. Technical Report TR96-01. Department of Mathematics and Statistics, University of Maryland; 1996. DOI: 10.1080/10556789808805699
Open DOI Search in Google Scholar Back to article
Browne S, Dongarra J, Grosse E, Rowan T. The netlib mathematical software repository. Corporation for National Research Initiatives. 1995. DOI: 10.1045/september95-browne
Open DOI Search in Google Scholar Back to article
Dobes J. A modified Markowitz criterion for the fast modes of the LU factorization. Proceedings of 48th Midwest Symposium on Circuits and Systems. 2005:955–959. DOI: 10.1109/MWSCAS.2005.1594261
Open DOI Search in Google Scholar Back to article
Yang Y. CurveLP-a MATLAB implementation of an infeasible interior-point algorithm for linear programming. Numerical Algorithms. 2017;74(4):967–996. DOI: 10.1007/s11075-016-0180-1
Open DOI Search in Google Scholar Back to article
Andersen ED. Finding all linearly dependent rows in large-scale linear programming. Optimization methods and software. 1995;6:219–227. DOI: 10.1080/10556789508805634
Open DOI Search in Google Scholar Back to article
Ng E, Peyton BW. Block sparse Cholesky algorithm on advanced uniprocessor computers. SIAM Journal on Scientific Computing. 1993;14:1034–1056. DOI: 10.1137/0914063
Open DOI Search in Google Scholar Back to article
Liu JW. Modification of the minimum degree algorithm by multiple elimination. ACM Transactions on Mathematical Software. 1985;11:141–153. DOI: 10.1145/214392.214398
Open DOI Search in Google Scholar Back to article
Guler O, den Hertog D, Roos C, Terlaky T, Tsuchiya T. Degeneracy in interior-point methods for linear programming: a survey. Annals of Operations Research. 1993;46:107–138. DOI: 10.1007/BF02096259
Open DOI Search in Google Scholar Back to article
Gill PE, Murray W, Saunders MA, Tomlin JA, Wright MH. On projected Newton barrier methods for linear programming and an equivalence of Karmarkar’s projective method. Mathematical Programming. 1986; 36;183–209. DOI: 10.1007/BF02592025
Open DOI Search in Google Scholar Back to article
Yang Y. Arc-search path-following interior-point algorithms for linear programming. Optimization Online. 2009.
Search in Google Scholar Back to article
Luenberger D. Linear and Nonlinear Programming, Second Edition. Addison-Wesley Publishing Company, Menlo Park; 1984.
Search in Google Scholar Back to article
Nocedal J, Wright S. Numerical Optimization. New York: Springer-Verlag; 1999. DOI: 10.1007/b98874
Open DOI Search in Google Scholar Back to article
Tits A, Yang Y. Globally convergent algorithms for robust pole assignment by state feedback. IEEE Transactions on Automatic Control. 1996;41(10):1432–1452. DOI: 10.1109/9.539425
Open DOI Search in Google Scholar Back to article