## 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 |

State | Published - Sep 2000 |

## ASJC Scopus subject areas

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