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...
| Main Author: | |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5199 |
| _version_ | 1826198203112882176 |
|---|---|
| author | Shapiro, Jeremy F., 1939- |
| author_facet | Shapiro, Jeremy F., 1939- |
| author_sort | Shapiro, Jeremy F., 1939- |
| collection | MIT |
| description | 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, generalized linear programming, group theory. |
| first_indexed | 2024-09-23T11:00:56Z |
| format | Working Paper |
| id | mit-1721.1/5199 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:00:56Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51992019-04-12T08:06:59Z Convergent Duality for the Traveling Salesman Problem Shapiro, Jeremy F., 1939- 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, generalized linear programming, group theory. 2004-05-28T19:27:40Z 2004-05-28T19:27:40Z 1989-11 Working Paper http://hdl.handle.net/1721.1/5199 en_US Operations Research Center Working Paper;OR 204-89 1744 bytes 879422 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Shapiro, Jeremy F., 1939- Convergent Duality for the Traveling Salesman Problem |
| title | Convergent Duality for the Traveling Salesman Problem |
| title_full | Convergent Duality for the Traveling Salesman Problem |
| title_fullStr | Convergent Duality for the Traveling Salesman Problem |
| title_full_unstemmed | Convergent Duality for the Traveling Salesman Problem |
| title_short | Convergent Duality for the Traveling Salesman Problem |
| title_sort | convergent duality for the traveling salesman problem |
| url | http://hdl.handle.net/1721.1/5199 |
| work_keys_str_mv | AT shapirojeremyf1939 convergentdualityforthetravelingsalesmanproblem |