Parallel primal-dual simplex algorithm

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

doi:10.1016/s0167-6377(00)00017-1

Parallel primal-dual simplex algorithm

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

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

20 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 language	English (US)
Pages (from-to)	47-55
Number of pages	9
Journal	Operations Research Letters
Volume	27
Issue number	2
DOIs	https://doi.org/10.1016/s0167-6377(00)00017-1
State	Published - Sep 2000

Funding

This work was supported by NSF grant DMI-9700285 and United Airlines, who also provided data for the computational experiments. Intel Corporation funded the parallel computing environment and ILOG provided the linear programming solver used in computational experiments.

ASJC Scopus subject areas

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

Access to Document

10.1016/s0167-6377(00)00017-1

Cite this

@article{1860d0d578c5464794eef8d8924d03a3,

title = "Parallel primal-dual simplex algorithm",

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.",

author = "Diego Klabjan and Johnson, {Ellis L.} and Nemhauser, {George L.}",

note = "Funding Information: This work was supported by NSF grant DMI-9700285 and United Airlines, who also provided data for the computational experiments. Intel Corporation funded the parallel computing environment and ILOG provided the linear programming solver used in computational experiments. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

year = "2000",

month = sep,

doi = "10.1016/s0167-6377(00)00017-1",

language = "English (US)",

volume = "27",

pages = "47--55",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Parallel primal-dual simplex algorithm

AU - Klabjan, Diego

AU - Johnson, Ellis L.

AU - Nemhauser, George L.

N1 - Funding Information: This work was supported by NSF grant DMI-9700285 and United Airlines, who also provided data for the computational experiments. Intel Corporation funded the parallel computing environment and ILOG provided the linear programming solver used in computational experiments. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2000/9

Y1 - 2000/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0034259216&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034259216&partnerID=8YFLogxK

U2 - 10.1016/s0167-6377(00)00017-1

DO - 10.1016/s0167-6377(00)00017-1

M3 - Article

AN - SCOPUS:0034259216

SN - 0167-6377

VL - 27

SP - 47

EP - 55

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -

Parallel primal-dual simplex algorithm

Abstract

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this