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

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 neighbourhood and the main characteristics of the presented algorithm are based on their approach. In addition, we use the algebraic equivalent transformation technique by Darvay to determine the search directions of the method.