Séminaire Lotharingien de Combinatoire, B21g (1989), 16 pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1990, 413/S-21, p. 127-140.]

A. Wanka

On First Experiences with the Implementation of a Newton Based Linear Programming Approach

Abstract. This paper presents the implementation of an exterior point linear programming approach introduced by Betke. In every iteration of this algorithm Newton's method is used in order to determine nearest points of two convex sets. The method is simple to implement, fully exploits sparsity and at the presence of rounding errors it achieves high precision and stability.

Beside the nice geometric proceeding a particular interest in this method is derived from the following observation: In Karmarkar's as well as in this algorithm one has to solve a linear equation system of the form A D2ATy = b. The solution of this system is the most time consuming part in linear programs. While in Karmarkar's method the entries of the diagonal Matrix D are the coordinates of the iteration point, the diagonal entries are either 0 or 1 in our method. Hence throughout this paper D is a purely combinatorial matrix which yields to reasonable numbers of rank one updates of the corresponding Cholesky factor of A D2AT. Moreover, the Cholesky factors become sparser than in Karmarkar's approach.

Math. Inst. der Universität zu Köln

The following versions are available: