Description
In 1984 Karmarkar presented a novel interior point method (IPM), which, as he claimed, was able to solve large-scale linear programs significantly faster than the simplex algorithm. This statement led to an explosion of interest in IPMs among researchers and practitioners. Indeed, the above resulted in an impressive progress in the theory and implementation technology of IPMs during the past 35 years. It is now widely accepted that IPMs are numerically reliable optimization tools and on large-scale problems they can significantly outperform the algorithms based on the simplex approach.
In the talk we give an overview about the state-of-the-art implementation techniques of IPMs. Since the practical success of any IPM implementation depends on the efficiency and the reliability of the linear algebra kernels in it, these issues will be in the focus of our survey.
We will discuss algorithms related to the efficient exploitation of sparsity and methods related to the numerical computations. A special emphasis will be given on the implementation techniques that exploit recent hardware architectures such as hierarchical memory structures, vector and parallel processing capabilities. The most relevant points of IPM implementations will be demonstrated by computational results to illustrate typical behavior of the presented implementation techniques.