A Novel Algorithm and Its Convergence for a Class of Combinatorial Optimization Problems
Zeng Yong · Gongcheng shuxue xuebao · 2004
The Hybrid LT scheme is a new type of schemes for combinatorial optimization problems. The constraints are divided into two parts. One is treated by Lagrange approach, and the other by penalty or barrier function. In cmparison with the existing Hop?eld type networks, the new scheme has several new features. It can be applicable to non-quadratic energy functions, and has reduced the dependence on arti?cial weighting parameters which have to be controlled externally. A new hybrid LT algorithm is proposed in this paper, by which we can ?nd a high quality solution quickly. In addition, the convergence on the proposed algortihm is investigated, and necessary condition and su?cient condition of convergence were given. The theoretical analysis and computer simulation results revealed that the proposed algorithm is e?cient and convergent for a very wide variety of combinatorial optimization problems.