Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

A globally convergent Lagrange and barrier function iterative algorithm for the traveling salesman problem.

C Dang1, L Xu

  • 1Department of Manufacturing Engineering & Engineering Management, City University of Hong Kong, Hong Kong. mecdang@cityu.edu.hl

Neural Networks : the Official Journal of the International Neural Network Society
|April 24, 2001
PubMed
Summary

A new iterative algorithm using Lagrange and barrier functions offers an effective solution for the Traveling Salesman Problem (TSP). This globally convergent method efficiently finds high-quality approximate solutions, outperforming existing algorithms like SoftAssign.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

[Analysis of current status in the construction of stroke centers and the quality of ischemic stroke medical care in Guangdong province (2023-2024)].

Zhonghua yi xue za zhi·2025
Same author

Energy deposition in liquid scintillators composed of CsPbBr<sub>3</sub> colloidal nanocrystal dispersions.

Nanoscale·2024
Same author

Biomarkers and Cognition Study, Singapore (BIOCIS): Protocol, Study Design, and Preliminary Findings.

The journal of prevention of Alzheimer's disease·2024
Same author

RUNX1-activated upregulation of lncRNA RNCR3 promotes cell proliferation, invasion, and suppresses apoptosis in colorectal cancer via miR-1301-3p/AKT1 axis in vitro and in vivo.

Clinical & translational oncology : official publication of the Federation of Spanish Oncology Societies and of the National Cancer Institute of Mexico·2020
Same author

Network change in the ipsilesional cerebellum is correlated with motor recovery following unilateral pontine infarction.

European journal of neurology·2019
Same author

Prospective evaluation of the cardiac safety of HER2-targeted therapies in patients with HER2-positive breast cancer and compromised heart function: the SAFE-HEaRt study.

Breast cancer research and treatment·2019

Area of Science:

  • Operations Research
  • Computer Science
  • Applied Mathematics

Background:

  • The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem with numerous real-world applications.
  • Existing algorithms for TSP, such as SoftAssign, have limitations in efficiency and solution quality.
  • Developing robust and efficient algorithms for TSP remains an active area of research.

Purpose of the Study:

  • To propose a novel, globally convergent iterative algorithm for approximating solutions to the Traveling Salesman Problem.
  • To address nonnegativity and linear equality constraints using an entropy-type barrier function and Lagrange multipliers, respectively.
  • To enhance solution quality by minimizing a barrier problem with a sequence of descending barrier parameters.

Main Methods:

Related Experiment Videos

  • The algorithm utilizes a combination of Lagrange multipliers and an entropy-type barrier function.
  • It iteratively searches for a minimum point of a barrier problem in a feasible descent direction.
  • Lagrange multipliers are updated using a globally convergent iterative procedure at each step.

Main Results:

  • The proposed algorithm demonstrates global convergence to a stationary point of the barrier problem.
  • Theoretical and numerical results indicate superior effectiveness and efficiency compared to the SoftAssign algorithm.
  • The method automatically satisfies nonnegativity constraints within a specific step length range.

Conclusions:

  • The developed Lagrange and barrier function iterative algorithm provides a promising approach for solving the Traveling Salesman Problem.
  • The algorithm's global convergence and efficiency suggest its potential for practical applications in optimization.
  • Further research may explore extensions and applications of this novel method to related combinatorial problems.