Global Optimization of Binary Quadratic Programming: A Neural Network Based Algorithm and Its FPGA Implementation

摘要

The global optimization of binary quadratic programming (BQP) has very important theory and wide application in various fields. Since BQP is a classic NP-hard problem, traditional algorithms will be very time-consuming when the dimension is very large. The neural network based algorithms have significant advantages in solving large scale optimization problems. However, directly applying neural network based algorithm cannot guarantee finding the global optimal solution of BQP. In this paper, we propose a neural network based algorithm for BQP by analyzing and utilizing geometric characteristics of the objective function isosurface and combining the advantages and properties of neural network as well as branch-and-bound method. Furthermore, the neural network algorithm is implemented with field-programmable gate array (FPGA) to take advantage of the parallel structure. System Generator which can be used to convert the design into HDL code automatically is adopted so that the calculation of upper and lower bounds can be deployed to FPGA. The numerical simulation illustrates the effectiveness and efficiency of the algorithm. Meanwhile, simulation results show the feasibility of applying the proposed algorithm to FPGA hardware.