A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation

Marianna E.-Nagy () and Anita Varga ()
Additional contact information
Marianna E.-Nagy: Budapest University of Technology and Economics
Anita Varga: Budapest University of Technology and Economics
Authors registered in the RePEc Author Service: Marianna Eisenberg-Nagy

Central European Journal of Operations Research, 2023, vol. 31, issue 3, No 2, 711 pages

Abstract: Abstract In this paper, we investigate a new primal-dual long-step interior point algorithm for linear optimization. Based on the step size, interior point algorithms can be divided into two main groups, short-step, and long-step methods. In practice, long-step variants perform better, but usually, a better theoretical complexity can be achieved for the short-step methods. One of the exceptions is the large-update algorithm of Ai and Zhang. The new wide neighborhood and the main characteristics of the presented algorithm are based on their approach. In addition, we use the algebraic equivalent transformation technique of Darvay to determine new modified search directions for our method. We show that the new long-step algorithm is convergent and has the best known iteration complexity of short-step variants. We present our numerical results and compare the performance of our algorithm with two previously introduced Ai-Zhang type interior point algorithms on a set of linear programming test problems from the Netlib library.

Keywords: Mathematical programming; Linear optimization; Interior point algorithms; Algebraic equivalent transformation technique (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10100-022-00812-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
Working Paper: A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation (2021)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:31:y:2023:i:3:d:10.1007_s10100-022-00812-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-022-00812-6

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().