Computational experience with a modified potential reduction algorithm for linear programming

Sanjay Mehrotra*, Kuo Ling Huang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We study the performance of a homogeneous and self-dual interior point solver for linear programming (LP) that is equipped with a continuously differentiable potential function. Our work is motivated by the apparent gap between the theoretical complexity results and long-step practical implementations in interior point algorithms. The potential function described here ensures a global linear polynomial-time convergence while providing the flexibility to integrate heuristics for generating the search directions and step length computations. Computational results on standard test problems show that LP problems are solved as efficiently (in terms of the number of iterations) as Mosek6.

Original languageEnglish (US)
Pages (from-to)865-891
Number of pages27
JournalOptimization Methods and Software
Volume27
Issue number4-5
DOIs
StatePublished - Oct 1 2012

Funding

The authors thank two anonymous referees for carefully reading this paper and giving several useful suggestions. The research of both authors was partially supported by ONR grants N00014-01-10048/P00002, N00014-09-10518, and NSF grant DMI-0522765. The research of both authors was partially supported by ONR grants N00014-01-10048/P00002, N00014-09-10518, and NSF grant DMI-0522765.

Keywords

  • homogeneous and self-dual model
  • interior point methods
  • linear programming

ASJC Scopus subject areas

  • Software
  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Computational experience with a modified potential reduction algorithm for linear programming'. Together they form a unique fingerprint.

Cite this