A Study on Reconfigurable Engine for Efficient Problem Solving for Combinatorial Optimization Problems

二次指派问题(QAP)是NP-Hard组合优化问题之一，用常规的优化方法很难得到最优解。在本研究中，我们研究了在短执行时间内解决二次指派问题的并行算法，并提出了一种有效地解决QAP问题的硬件算法。该算法基于禁忌搜索，其主体是一种脉动算法，运行在简单处理单元的一维阵列上。在算法执行过程中，并行评估多个邻域解，并以流水线方式评估每个解。该算法有效地利用了近期大规模现场可编程门阵列的内部块RAM。用Verilog-HDL语言设计了硬件QAP求解器，并在一块FPGA板上实现。实验结果表明了该算法的有效性和有效性。本研究的成果已在多个国内外会议上发表。

The quadratic assignment problem (QAP), which is one of NP-hard combinatorial optimization problems, is known to be difficult to be solved optimally with ordinary optimization methods. In this research, we investigated parallel algorithms to solve the quadratic assignment problem in a short execution time, and proposed a hardware algorithm to efficiently solve the QAP. The proposed algorithm is based on tabu search, and its main body is a systolic algorithm, which runs on a one-dimensional array of simple processing units. During the algorithm execution, multiple neighborhood solutions are evaluated in parallel and each solution is evaluated in a pipeline fashion. The proposed algorithm effectively utilizes internal block RAMs of recent large scale FPGAs. The proposed hardware QAP solver was designed with Verilog-HDL, and implemented on a FPGA board. Experimental results showed the efficiency and effectiveness of the proposed algorithm. Results obtained by this research have been presented in several domestic and international conferences.