## Optimization and Systems Theory Seminar

Department of Mathematics, KTH

### Erling D. Andersen

Department of Management,

Odense University,

Campusvej 55,

DK - 5230 Odense M,

Denmark.

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.

Calendar of Seminars

*Last update: September 27, 1996 by Anders Forsgren,
andersf@math.kth.se.
*