A Parallel, Linear Programming-based Heuristic for Large-Scale Set Partitioning Problems
提出一种并行线性规划与蕴含推理结合的启发式算法，用于在分布式内存计算机上求解大规模集合划分问题，通过预处理、探测、原始启发式和割生成等技术并行化，能在合理时间内获得困难问题的解。
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 primaldual 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.