Affordable Access

Publisher Website

Computational experience with a primal-dual interior point method for linear programming

Authors
Journal
Linear Algebra and its Applications
0024-3795
Publisher
Elsevier
Publication Date
Volume
152
Identifiers
DOI: 10.1016/0024-3795(91)90275-2
Disciplines
  • Computer Science

Abstract

Abstract A new comprehensive implementation of a primal-dual algorithm for linear programming is described. It allows for easy handling of simple bounds on the primal variables and incorporates free variables, which have not previously been included in a primal-dual implementation. We discuss in detail a variety of computational issues concerning the primal-dual implementation and barrier methods for linear programming in general. We show that, in a certain way, Lustig's method for obtaining feasibility is equivalent to Newton's method. This demonstrates that the method is in some sense the natural way to reduce infeasibility. The role of the barrier parameter in computational practice is studied in detail. Numerical results are given for the entire expanded NETLIB test set for the basic algorithm and its variants, as well as version 5.3 of MINOS.

There are no comments yet on this publication. Be the first to share your thoughts.