Solving 0-1 quadratic problems with two-level parallelization of the BiqCrunch solver

摘要

In this paper we present MLTBiqCrunch, a hierarchically parallelized version of the open-source solver BiqCrunch [1]. More precisely, this version has two levels of parallelization: a coarse grain, assigning a thread to a node evaluation and a fine grain, parallelizing a node evaluation when some threads are not busy. We present experiments on some classical binary quadratic optimization problems with comparison of their scalability and raw performance. In particular, we obtain a superlinear speedup for some of the most difficult instances.