Optimization Online


Implementation of Interior-point Methods for LP based on Krylov Subspace Iterative Solvers with Inner-iteration Preconditioning

Yiran Cui(y.cui.12***at***ucl.ac.uk)
Keiichi Morikuni(morikuni***at***cs.tsukuba.ac.jp)
Takashi Tsuchiya(tsuchiya***at***grips.ac.jp)
Ken Hayami(hayami***at***nii.ac.jp)

Abstract: We apply novel inner-iteration preconditioned Krylov subspace methods to the interior-point algorithm for linear programming (LP). Inner-iteration preconditioners recently proposed by Morikuni and Hayami enable us to overcome the severe ill-conditioning of linear equations solved in the final phase of interior-point iterations. The employed Krylov subspace methods do not suffer from rank-deficiency and therefore no preprocessing is necessary even if rows of the constraint matrix are not linearly independent. Extensive numerical experiments are conducted over diverse instances of 125 LP problems including Netlib, QAPLIB, and Mittelmann’s collections. The number of variables of the largest problem is 434,580. It turns out that our implementation is more stable and robust than the standard public domain solvers SeDuMi (Self-Dual Minimization) and SDPT3 (Semidefinite Programming Toh-Todd-Tütüncü) without increasing CPU time. As far as we know, this is the first result that an interior-point method entirely based on iterative solvers succeed in solving a fairly large number of standard LP instances from benchmark libraries under the standard stopping criteria.

Keywords: linear programming problems, interior-point methods, inner-iteration preconditioning, Krylov subspace methods

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 04/25/2016
Entry Accepted: 04/26/2016
Entry Last Modified: 04/25/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society