Load balancing in hypercube solution of stochastic optimization problems

In some stochastic optimization problems the error bounds computed for the expected optimum can be decreased through recursive divide-and-conquer methods based on partitioning the support of the random variables. Each generated partition from the divide-and-conquer process can be treated independently. This class of problems is therefore easy to parallelize, and we describe two parallel implementations of this divide-and-conquer algorithm applied to PERT. Our results indicate that parallel processing and divide-and-conquer are indeed feasible and efficient for problems of this type. The tests were done on an Intel iPSC/2 multicomputer with 16 nodes.