Optimization and Systems Theory Seminar
Department of Mathematics, KTH

Erling D. Andersen
Department of Management,
Odense University,
Campusvej 55,
DK - 5230 Odense M,
E-mail: eda@busieco.ou.dk
Homepage: http://www.samnet.ou.dk/~eda/

Interior-point methods for linear programming

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.

Back Calendar of Seminars
Last update: September 27, 1996 by Anders Forsgren, andersf@math.kth.se.