HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Dang, C. Articles by Xu, L. Search for Related Content PubMed PubMed Citation Articles by Dang, C. Articles by Xu, L.

A Lagrange Multiplier and Hopfield-Type Barrier Function Method for the Traveling Salesman Problem

mecdang{at}cityu.edu.hk, Department of Manufacturing Engineering and Engineering Management, City University of Hong Kong, Kowloon, Hong Kong

Lei Xu

lxu{at}cse.cuhk.edu.hk, Department of Computer Science and Engineering, Chinese University of Hong Kong, New Territories, Hong Kong

A Lagrange multiplier and Hopfield-type barrier function method is proposed for approximating a solution of the traveling salesman problem. The method is derived from applications of Lagrange multipliers and a Hopfield-type barrier function and attempts to produce a solution of high quality by generating a minimum point of a barrier problem for a sequence of descending values of the barrier parameter. For any given value of the barrier parameter, the method searches for a minimum point of the barrier problem in a feasible descent direction, which has a desired property that lower and upper bounds on variables are always satisfied automatically if the step length is a number between zero and one. At each iteration, the feasible descent direction is found by updating Lagrange multipliers with a globally convergent iterative procedure. For any given value of the barrier parameter, the method converges to a stationary point of the barrier problem without any condition on the objective function. Theoretical and numerical results show that the method seems more effective and efficient than the softassign algorithm.

This article has been cited by other articles:

				Q. J. M. Huys, R. S. Zemel, R. Natarajan, and P. Dayan Fast population coding. Neural Comput., February 1, 2007; 19(2): 404 - 441. [Abstract] [Full Text] [PDF]