Quadratic Assignment Problems are a class of NP-hard combinatorial optimization problems with a wide range of real-world applications such as Vehicle Routing and FPGA Block Placement. Despite technological advances, solvers that target Quadratic Assignment Problems still require significant computing resources and time, especially as problem sizes grow; with the end of Dennard Scaling leading to the increased development of domain-specific hardware for such tasks. This paper presents MAQO: a hardware architecture for a scalable many-core annealer for quadratic optimization, implemented on an Intel Stratix 10 FPGA. MAQO is comprised of 32 domain-specific processing cores, supporting Quadratic Assignment Problems with up to 200 integer variables, in combination with a Parallel Tempering controller, all operating at 220MHz with a maximum FPGA power draw of 40W. We benchmark MAQO's performance, via solving some of the most difficult known Quadratic Assignment Problem instances, and show that it is, on average, 2.5 times faster than the next best competing solver with 22 times better performance-per-watt.

Assignment Problems are a class of NP-hard combinatorial optimization problems with a wide range of real-world applications such as Vehicle Routing and FPGA Block Placement. Despite technological advances, solvers that target Assignment Problems still require significant computing resources and time, especially as problem sizes grow. This paper introduces novel cost function formulations to leverage vector processing elements in accelerating local search algorithms for solving Quadratic Assignment and Semi-Assignment problems. We incorporate these vectorization methods within a Parallel Tempering framework to solve some of the most difficult known Quadratic Assignment and Semi-Assignment Problems up to sizes of 729 integer variables and show that this solver system can perform upwards of 300 times faster than other state-of-the-art solvers. We then conduct experiments to quantify the performance and scaling of these vectorization methods and qualify their situational strengths and trade-offs for use in future algorithms and hardware systems.

Boltzmann Machines are recurrent neural networks that have been used extensively in combinatorial optimization due to their simplicity and ease of parallelization. This paper introduces the Permutational Boltzmann Machine, a neural network capable of solving permutation optimization problems. We implement this network in combination with a Parallel Tempering algorithm with varying degrees of parallelism ranging from a single-thread variant to a multi-threaded system using a 64-core CPU with SIMD instructions. We benchmark the performance of this new system on Quadratic Assignment Problems, using some of the most difficult known instances, and show that our parallel system performs in excess of 100 $$\times $$ faster than any known dedicated solver, including those implemented on CPU clusters, GPUs, and FPGAs.