Splitting dense columns of constraint matrix in interior point methods for large scale linear programming1,2

Research output: Contribution to journalArticlepeer-review

Abstract

A method is proposed for handling dense columns of the constraint matrix of large scale linear programming problems. Such columns are known to create dense windows in the matrices AAT which are inverted at every iteration of the interior point method. Consequently, Cholesky factor of AAT becomes dense, which degrades the efficiency of the LP code. In the method considered, all dense columns are then split into shorter ones. One dense AAT window of large size is thus replaced with p windows each of size p times smaller, leading to a remarkable reduction of the number of nonzeros in the matrix to be inverted and in its Cholesky factor.

Original languageEnglish
Pages (from-to)285-297
Number of pages13
JournalOptimization
Volume24
Issue number3-4
DOIs
Publication statusPublished - 1 Jan 1992

Keywords

  • dense columns
  • Karmarkar’s projections
  • linear programming

Fingerprint Dive into the research topics of 'Splitting dense columns of constraint matrix in interior point methods for large scale linear programming<sup>1,2</sup>'. Together they form a unique fingerprint.

Cite this