Implementation of an interior point method with basis preconditioning
- PDF / 468,943 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 45 Downloads / 193 Views
Implementation of an interior point method with basis preconditioning Lukas Schork1 · Jacek Gondzio1 Received: 21 September 2018 / Accepted: 5 February 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract The implementation of a linear programming interior point solver is described that is based on iterative linear algebra. The linear systems are preconditioned by a basis matrix, which is updated from one interior point iteration to the next to bound the entries in a certain tableau matrix. The update scheme is based on simplex-type pivot operations and is implemented using linear algebra techniques from the revised simplex method. An initial basis is constructed by a crash procedure after a few interior point iterations. The basis at the end of the interior point solve provides the starting basis for a crossover method which recovers a basic solution to the linear program. Results of a computational study on a diverse set of medium to large-scale problems are discussed. Keywords Linear programming · Interior point methods · Basis preconditioning · Crossover Mathematics Subject Classification 90C05 · 90C06 · 90C51
1 Introduction The purpose of this paper is to describe a new linear programming (LP) interior point solver called IPX that is based on iterative linear algebra. IPX uses an approach originally implemented in [1,19] that employs a basis matrix as preconditioner for the linear systems. In the previous works the basis was chosen as the first m linearly inde-
Supported by Google Research Award “Fast interior point method for linear programming problems”.
B
Lukas Schork [email protected] Jacek Gondzio [email protected]
1
School of Mathematics, University of Edinburgh, Edinburgh EH9 3FD, Scotland, UK
123
L. Schork, J. Gondzio
pendent columns of the LP constraint matrix A ∈ Rm×n , after ordering the columns by taking scaling factors from the current interior point iterate into account. (In [1] the scaling factors were used for ordering, whereas in [19] the 1-norm of the scaled columns was used.) Although this yields a perfect preconditioner close to the solution of a nondegenerate LP model, the success of the method was limited in practice. The core of IPX is a new method for basis selection. A starting basis is constructed after a few interior point iterations and subsequently updated in an attempt to maintain “maximum volume”. The maximum volume criterion is known from rank revealing matrix factorizations (see, for example, [21]) and bounds the condition number of the preconditioned matrices in terms of the dimension of the LP model [3,25]. Because finding a maximum volume basis is computationally impractical for largescale problems, the implementation is based on a heuristic that efficiently finds a basis of comparable quality. The required linear algebra operations are those from the revised simplex method, for which established and highly optimized computational techniques exist. Section 2 sketches the interior point algorithm and disc
Data Loading...
