A Parallel, Linear Programming Based Heuristic for Large Scale Set Partitioning Problems

Jeff Linderoth (linderotmcs.anl.gov)
Eva Lee (evakyleeisye.gatech.edu)
Martin Savelsbergh (mwpsisye.gatech.edu)

Abstract: We describe a parallel, linear programming and implication based heuristic for solving set partitioning problems on distributed memory computer architectures. Our implementation is carefully designed to exploit parallelism to greatest advantage in advanced techniques like preprocessing and probing, primal heuristics, and cut generation. A primal-dual subproblem simplex method is used for solving the linear programming relaxation, which breaks the linear programming solution process into natural phases from which we can exploit information to find good solutions on the various processors. Implications from the probing operation are shared among the processors. Combining these techniques allows us to obtain solutions to large and difficult problems in a reasonable amount of computing time.

Keywords: Set Partitioning, Integer Programming, Parallel Computing

Category 1: Integer Programming (0-1 Programming )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Applications -- OR and Management Sciences (Airline Optimization )

Citation: TLI-99-07, The Logistics Institute, Georgia Tech

Download: [Postscript]

Entry Submitted: 08/21/2000
Entry Last Modified: 08/21/2000

Modify/Update this entry