Anomalous Acceleration in Parallel Multiple-Cost-Row Linear Programming

Earlier parallel computational results on constrained global optimization problems have shown that speedups greater than the number of processors can occur in practice. To show how this is possible, a relatively simple example of a multiple-cost-row linear program is presented in which the parallel algorithm gives a speedup, over its sequential version, greater than the number of processors. In addition, it is shown that for a particular problem instance (taken from another special class of multiple-cost-row linear programming problems), the average parallel speedup, taken over all orderings of the cost rows, can also be greater than the number of processors.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.