It is now accepted that interior-point methods are an efficient alternative to the simplex method when solving sufficiently large LP problems. The purpose of this talk is to present the interior-point methods implemented in the LP codes, which leads to this efficiency. First, we review the primal-dual algorithm which forms the basis for all commercially available software. Unfortunately, this algorithm cannot detect a possible infeasible or unbounded status of the LP problem. However, the so-called homogeneous model presents an elegant solution to this problem about detecting primal or dual infeasibility. The efficiency of the interior-point methods is highly dependent on the linear algebra used in the implementation. Therefore, we will dicuss linear algebra issues related to interior-point methods in some detail. Moreover, we present computational results demonstrating the speed-up, which can be obtained using a parallel SGI Challenge computer. Finally, it is well-known that interior-point methods do not generate an optimal solution, which is also a basic solution if the LP has multiple optimal solution. This is sometimes a major drawback in practice. Therefore, a basis identification procedure is required and we present one such procedure.
Calendar of Seminars