Scalable Parallel Branch-and-Bound with Relaxed Concurrent Queues - A Study of Relaxed Concurrent Queues in Branch-and-Bound using a Generic Solver Framework

Abstract

Relaxed concurrent queues improve scalability by weakening strict ordering guarantees in exchange for reduced synchronisation overhead and contention. While previous work has demonstrated strong performance for such data structures in isolation, their applicability within complete algorithms and practical workloads remains less explored. This thesis investigates the use of relaxed concurrent queues, particularly the MultiQueue and related relaxed concurrent data structures, in branch-and bound (BnB) algorithms. A literature study identifies BnB as a suitable application domain due to its tolerance for non-strict exploration order, after which a generic modular framework for parallel BnB solving is developed. The framework separates problem-specific logic from parallel execution and queue management, greatly simplifying the development of high-performing branch-and-bound solvers. The framework is evaluated primarily through a case study on the Maximum Clique Problem using DIMACS benchmark instances on a 512-thread multicore system, alongside demonstrations on knapsack variants. The experimental results show that relaxed concurrent designs generally scale better than strict concurrent alternatives under high contention, with relaxed queues significantly outperforming strict concurrent counterparts while maintaining competitive search quality. Solvers using our framework with relaxed concurrent data structures sometimes outperform competitors, showing the value and further potential of our framework. The results demonstrate that data-structure-level parallelism based on relaxed concurrent queues can compete with algorithm-level parallelisation strategies in several cases, particularly at very high thread counts.