On finding a vertex solution using interior point methods

Sanjay Mehrotra*

*Corresponding author for this work

Research output: Contribution to journalArticle

32 Scopus citations

Abstract

An approach is proposed to generate a vertex solution while using a primal-dual interior point method to solve linear programs. A controlled random perturbation is made to the cost vector. A method to identify the active constraints at the vertex to which the solutions are converging is given. This basic method is further refined to save computational effort. The proposed approach is tested by using a variation of the primal-dual interior point method. Our method is developed by taking a predictor-corrector approach. In practice this method takes considerably fewer iterations to solve linear programs than methods described by Choi, Monma, and Shanno; Lustig, Marsten, and Shanno; and Domich, Boggs, Donaldson, and Witzgall. Computational results on problems from the NETLIB test set are reported to test our approach for finding vertex solutions. These results show that one perturbation is enough to force the solutions to converge to a vertex. The results indicate that the proposed approach is insensitive to the number of degenerate variables. The results also indicate that the effort required to generate a vertex solution is comparable to that required to solve the problem using an interior point method.

Original languageEnglish (US)
Pages (from-to)233-253
Number of pages21
JournalLinear Algebra and Its Applications
Volume152
Issue numberC
DOIs
StatePublished - Jul 1 1991

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On finding a vertex solution using interior point methods'. Together they form a unique fingerprint.

  • Cite this