Convergent Duality for the Traveling Salesman Problem

Convergent Duality for the Traveling Salesman Problem

A constructive method is presented for optimizing exactly the Traveling Salesman Problem as a sequence of shortest route problems. The method combines group theoretic and Lagrangean relaxation constructions. Key Words: Traveling Salesman Problem, Lagrangean relaxation, shortest route problem, genera...

Full description

Bibliographic Details
Main Author:	Shapiro, Jeremy F., 1939-
Format:	Working Paper
Language:	en_US
Published:	Massachusetts Institute of Technology, Operations Research Center 2004
Online Access:	http://hdl.handle.net/1721.1/5199

Similar Items

The Travelling Salesman Problem and Related Problems
by: Gavish, Bezalel, et al.
Published: (2004)

Traveling salesman path problems
by: Lam, Fumei
Published: (2006)

Probabilistic Traveling Salesman Problems
by: Jaillet, Patrick
Published: (2005)

An algorithm for the traveling salesman problem,
by: Little, John D. C.
Published: (2009)

Constructive Duality in Integer Programming
by: Fisher, Marshall L., et al.
Published: (2004)

Computational Complexity and the Traveling Salesman Problem
by: Johnson, David, et al.
Published: (2023)

Trajectory Stability in the Traveling Salesman Problem
by: Sánchez, Sergio, et al.
Published: (2018)

Algoritma polinomial dan traveling salesman problem
by: , WIDYASTUTI, Naniek, et al.
Published: (1999)

Online traveling salesman problems with rejection options
by: Jaillet, Patrick, et al.
Published: (2015)

Online Traveling Salesman Problems with Service Flexibility
by: Jaillet, Patrick, et al.
Published: (2011)

Two traveling salesman facility location problems
Published: (2003)

An arc flow formulation for the travelling salesman problem
by: Claus, A.
Published: (2009)

The Traveling Salesman Problem for Systems with Dynamic Constraints
by: Adler, Aviv
Published: (2023)

On semidefinite programming relaxations of the traveling salesman problem
by: De Klerk, Etienne., et al.
Published: (2009)

The Traveling Salesman Problem and orienteering for kinodynamic vehicles
by: Adler, Aviv
Published: (2018)

On the Stochastic Travelling Salesman problem for the Dubin's vehicle
by: Itani, Sleiman M
Published: (2007)

On semidefinite programming relaxations of the traveling salesman problem
by: Klerk, E, et al.
Published: (2008)

On semidefinite programming relaxations of the traveling salesman problem
by: Klerk, E, et al.
Published: (2009)

Swarm intelligence algorithms’ solutions to the travelling salesman’s problem
by: Odili, Julius Beneoluchi, et al.
Published: (2020)

On the spacefilling curve heuristic for the Eculidean traveling salesman problem
by: Bertsimas, Dimitris., et al.
Published: (2009)

Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem
by: Williamson, D.P.
Published: (2023)

Graph convolutional neural networks for the travelling salesman problem
by: Joshi, Chaitanya Krishna
Published: (2019)

Genetic algorithm to optimize routing problem modelled as the travelling salesman problem
by: Muhammad Azrul Faiz , Nor Adzmi
Published: (2013)

Simulated annealing with probabilistic analysis for solving traveling salesman problems
by: Hong, Pei Yee, et al.
Published: (2013)

An improved tabu search for solving symmetric traveling salesman problems
by: Lim, Yai Fung, et al.
Published: (2011)

Modified reactive tabu search for the symmetric traveling salesman problems
by: Lim, Yai Fung, et al.
Published: (2013)

Tutorials on African Buffalo Optimization for Solving the Travelling Salesman Problem
by: Odili, Julius Beneoluchi, et al.
Published: (2017)

Solving the Traveling Salesman’s Problem using the African Buffalo Optimization
by: Odili, Julius Beneoluchi, et al.
Published: (2016)

Algorithms for a scheduling application of the Asymmetric Traveling Salesman Problem.
by: Kanellakis, Paris C
Published: (2005)

Special cases of traveling salesman and repairman problems with time windows
Published: (2003)

Memetic framework with adaptive meme pool for the travelling salesman problem
by: Zeng, Yuntao
Published: (2023)

Constructive Duality for Mixed Integer Programming: Part I, Theory
by: Hiller, Randall S., et al.
Published: (2004)

Finding long chains in kidney exchange using the traveling salesman problem
by: Ashlagi, Itai, et al.
Published: (2015)

Bee colony optimisation of the travelling salesman problem in light rail systems
by: Wang, Chen, et al.
Published: (2019)

New heuristic function in ant colony system for the travelling salesman problem
by: Alobaedy, Mustafa Muwafak, et al.
Published: (2012)

Performance evaluation of heuristic methods in solving symmetric travelling salesman problems
by: Lim, Yai-Fung, et al.
Published: (2016)

Enhanced selection method for genetic algorithm to solve traveling salesman problem
by: Jubeir, Mohammed, et al.
Published: (2017)

A GPU accelerated parallel genetic algorithm for the traveling salesman problem
by: Binjubier, Mohammed, et al.
Published: (2024)

Probabilistic analysis of the 1-tree relaxation for the Eculidean traveling salesman problem
by: Goemans, Michel X., et al.
Published: (2009)

Optimizing Traveling Salesman Problem in Multi-Agent Systems with Practical Constraints
by: Yang, Ruixiao
Published: (2024)