ArcLP: A Matlab Implementation of an 𝒪(√nL) Arc-search Infeasible Interior-Point Algorithm for Linear Programming
By: Yaguang Yang
References
- Dantzig GB. Programming in a linear structure. Econometrica. 1949;17:200–211. DOI: 10.2307/1905523
- Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorics. 1984;4:373–395. DOI: 10.1007/BF02579150
- 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 - Mehrotra S. On the implementation of a primal-dual interior point method. SIAM Journal on Optimization. 1992;2:575–601. DOI: 10.1137/0802028
- 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
- 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
- Todd MJ. The many facets of linear programming. Mathematical Programming, Ser. B. 2002;91:417–436. DOI: 10.1007/s101070100261
- Wright S. Primal-dual interior-point methods. SIAM. 1995.
- 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 - 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
- Mathworks. Optimization Toolbox: User’s Guide. 2019.
- 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 - Browne S, Dongarra J, Grosse E, Rowan T. The netlib mathematical software repository. Corporation for National Research Initiatives. 1995. DOI: 10.1045/september95-browne
- 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
- 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
- Andersen ED. Finding all linearly dependent rows in large-scale linear programming. Optimization methods and software. 1995;6:219–227. DOI: 10.1080/10556789508805634
- 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
- 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
- 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
- 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
- Yang Y. Arc-search path-following interior-point algorithms for linear programming. Optimization Online. 2009.
- Luenberger D. Linear and Nonlinear Programming, Second Edition. Addison-Wesley Publishing Company, Menlo Park; 1984.
- Nocedal J, Wright S. Numerical Optimization. New York: Springer-Verlag; 1999. DOI: 10.1007/b98874
- 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
DOI: https://doi.org/10.5334/jors.674 | Journal eISSN: 2049-9647
Language: English
Page range: 57 - 57
Submitted on: Jan 11, 2026
Accepted on: Jul 28, 2026
Published on: Aug 12, 2026
Published by: Ubiquity Press
In partnership with: Paradigm Publishing Services
© 2026 Yaguang Yang, published by Ubiquity Press
This work is licensed under the Creative Commons Attribution 4.0 License.