Solving the Assignment Problem Using Continuous-Time and Discrete-Time Improved Dual Networks

Author

Xiaolin Hu ; Jun Wang

Author_Institution

Dept. of Comput. Sci. & Technol., Tsinghua Univ., Beijing, China

Volume

23

Issue

5

fYear

2012

fDate

5/1/2012 12:00:00 AM

Firstpage

821

Lastpage

827

Abstract

The assignment problem is an archetypal combinatorial optimization problem. In this brief, we present a continuous-time version and a discrete-time version of the improved dual neural network (IDNN) for solving the assignment problem. Compared with most assignment networks in the literature, the two versions of IDNNs are advantageous in circuit implementation due to their simple structures. Both of them are theoretically guaranteed to be globally convergent to a solution of the assignment problem if only the solution is unique.

Keywords

analogue circuits; combinatorial mathematics; electronic engineering computing; neural nets; optimisation; IDNN; archetypal combinatorial optimization problem; assignment problem; circuit implementation; continuous-time improved dual networks; discrete-time improved dual networks; improved dual neural network; Biological neural networks; Convergence; Equations; Learning systems; Neurons; Trajectory; Upper bound; Analog circuits; assignment problem; linear programming; quadratic programming; sorting problem;

fLanguage

English

Journal_Title

Neural Networks and Learning Systems, IEEE Transactions on

Publisher

ieee

ISSN

2162-237X

Type

jour

DOI

10.1109/TNNLS.2012.2187798

Filename

6155745