Sensitivity Analysis for Shortest Hamiltonian Path and Traveling Salesman Problems
Abstract
The problem considered in this paper belongs to so called sensitivity analysis in combinatorial optimization. This term is used for a phase of solution procedure when an optimal solution of problem has been already found and additional calculations are performed in order to investigate, how this optimal solution depends on changes of problems parameters. In this paper two well known combinatorial optimization problems are considered: the shortest Hamiltonian path problem in undirected weighted graph and the symmetric traveling salesman problem. It is assumed that an optimal solution of given problem is known. The goal of sensitivity analysis consists in finding by how much we can perturb each edge weight individually without changing the optimality of the solution. The maximum increment and decrement of the edge weight that preserve the optimality of solution are called the edge tolerances with respect to this solution. In this paper, a method of computing lower bounds of the edge tolerances with respect to the optimal solution of the shortest Hamiltonian path problem and traveling salesman problem is described. The method is based on solving the sensitivity analysis problem for appropriate relaxation of the original optimization problem. This paper gives a description of the approach and its microcomputer implementation and we report preliminary results of computational experiments. (kr)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1988
- Accession Number
- ADA197167
Entities
People
- Marek Libura
Organizations
- Carnegie Mellon University