Performances of randomized work scheduling for parallel depth-first tree search discrete optimization problems

Given a discrete optimization problem that is solved by an exhaustive depth first tree search, a method of solving the optimization problem in parallel is to perform a preliminary bounded search to seed a work queue that is then divided among multiple processors to complete the search of the sub-trees in the work queue. If pruning decisions are made during the search with knowledge of the best-seen solution at the time of the pruning decision, then work scheduling can affect performance of the program based on the distribution of solutions in terms of optimality. We show that a randomized work-scheduling algorithm generally provides performance better than half way between the performances of scheduling algorithms that implement a left to right traversal of the search tree or a right to left traversal. Often performance of the random work scheduling is near the better of the two traditional methods and can actually outperform both.