A Dual Neural Network Scheme for Solving the Assignment Problem

The assignment problem is an archetypal combinatorial optimization problem. This paper presents a neural network based on a dynamic model for solving the assignment problem. The main idea is to replace the assignment problem with a linear programming problem. On the basis of the Karush-Kuhn- Tucker optimality conditions, the equilibrium point of the proposed neural network is proved to be equivalent to the optimal solution of the original problem. It is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the assignment problem. Block diagram of the proposed model is given. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.