Primal-dual interior point method for linear programming based on a new wide neighborhood

Abstract

This work is devoted to the theoretical and numerical study of interior-point meth- ods, and more specifically, central-path primal-dual algorithms for linear program- ming. Recognized for their polynomial complexity, convergence rate, and numerical efficiency, these approaches are enhanced here by the introduction of a new large neighborhood developed by Darvay in 2018. The proposed algorithm is polynomial in time and achieves the best complexity bound known to date for interior-point methods applied to linear programming. Finally, this dissertation concludes with a numerical study that demonstrates the practical effectiveness of the proposed approach