Parallel Combinatorial Optimization with Decision Diagrams

Abstract. We propose a new approach for parallelizing search for com-binatorial optimization that is based on a recursive application of approx-imate Decision Diagrams. This generic scheme can, in principle, be ap-plied to any combinatorial optimization problem for which a decision dia-gram representation is available. We consider the maximum independent set problem as a specific case study, and show how a recently proposed sequential branch-and-bound scheme based on approximate decision di-agrams can be parallelized efficiently using the X10 parallel program-ming and execution framework. Experimental results using our parallel solver, DDX10, running on up to 256 compute cores spread across a clus-ter of machines indicate that parallel decision diagrams scale effectively and consistently. Moreover, on graphs of relatively high density, paral-lel decision diagrams often outperform state-of-the-art parallel integer programming when both use a single 32-core machine.