Deep Neural Networks for Linear Sum Assignment Problems

Abstract

Many resource allocation issues in wireless communications can be modeled as assignment problems and can be solved online with global information. However, traditional methods for assignment problems take a lot of time to find the optimal solutions. In this letter, we solve the assignment problem using machine learning approach. Specifically, the linear sum assignment problems (LSAPs) are solved by the deep neural networks (DNNs). Since LSAP is a combinatorial optimization problem, it is first decomposed into several sub-assignment problems. Each of them is a classification problem and can be solved effectively with DNNs. Two kinds of DNNs, feed-forward neural network and convolutional neural network, are implemented to deal with the sub-assignment problems, respectively. Based on computer simulation, DNNs can effectively solve LSAPs with great time efficiency and only slight loss of accuracy.