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 -