Prior reduced fill-in in solving equations in interior point algorithms

John R. Birge, Robert M. Freund, Robert Vanderbei

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

The efficiency of interior-point algorithms for linear programming is related to the effort required to factorize the matrix used to solve for the search direction at each iteration. When the linear program is in symmetric form (i.e., the constraints are Ax ≤ b, x ≥ 0), then there are two mathematically equivalent forms of the search direction, involving different matrices. One form necessitates factoring a matrix whose sparsity pattern has the same form as that of (AAT). The other form necessitates factoring a matrix whose sparsity pattern has the same form as that of (ATA). Depending on the structure of the matrix A, one of these two forms may produce significantly less fill-in than the other. Furthermore, by analyzing the fill-in of both forms prior to starting the iterative phase of the algorithm, the form with the least fill-in can be computed and used throughout the algorithm. Finally, this methodology can be applied to linear programs that are not in symmetric form, that contain both equality and inequality constraints.

Original languageEnglish (US)
Pages (from-to)195-198
Number of pages4
JournalOperations Research Letters
Volume11
Issue number4
DOIs
StatePublished - May 1992

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Keywords

  • factorization
  • fill-in
  • interior-point algorithm
  • linear program

Fingerprint Dive into the research topics of 'Prior reduced fill-in in solving equations in interior point algorithms'. Together they form a unique fingerprint.

  • Cite this