Parallel primal-dual simplex algorithm

Diego Klabjan, Ellis L. Johnson, George L. Nemhauser

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

Recently, the primal-dual simplex method has been used to solve linear programs with a large number of columns. We present a parallel primal-dual simplex algorithm that is capable of solving linear programs with at least an order of magnitude more columns than the previous work. The algorithm repeatedly solves several linear programs in parallel and combines the dual solutions to obtain a new dual feasible solution. The primal part of the algorithm involves a new randomized pricing strategy. We tested the algorithm on instances with thousands of rows and tens of millions of columns. For example, an instance with 1700 rows and 45 million columns was solved in about 2 h on 12 processors.

Original languageEnglish (US)
Pages (from-to)47-55
Number of pages9
JournalOperations Research Letters
Volume27
Issue number2
StatePublished - Sep 2000

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Parallel primal-dual simplex algorithm'. Together they form a unique fingerprint.

Cite this