A Single Deep Neural Network Model for Multiobjective Unconstrained Binary Quadratic Programming Problem

The multiobjective unconstrained binary quadratic programming problem is an important combinatorial optimization problem with both theory and practical values. Until now, several efforts have been made to design metaheuristic methods to solve the problem. However, designing such effective methods is not trivial and heavily depends on experts' specific knowledge. Meanwhile, due to the iterative nature of metaheuristic methods, they require a long time to find high-quality solutions. From the perspective of machine learning, this paper proposes a deep reinforcement learning method to solve the problem. The method can automatically learn effective heuristics from a large amount of data, thus decreasing the need for experts' knowledge. Meanwhile, by leveraging the power of GPU, the method can quickly obtain high-quality solutions for a batch of instances. Experimental results show the proposed method outperforms two classical metaheuristic methods in terms of solution quality and running time for solving the problem.