×

Stability aspects of the traveling salesman problem based on \(k\)-best solutions. (English) Zbl 0910.90264

Summary: This paper discusses stability analysis for the traveling salesman problem (TSP). For a traveling salesman tour which is known to be optimal with respect to a given instance (length vector) we are interested in determining the stability region, i.e. the set of all length vectors for which the tour is optimal. The following three subsets of the stability region are of special interest: (1) tolerances, i.e. the maximum perturbations of single edges; (2) tolerance regions which are subsets of the stability region that can be constructed from the tolerances; and (3) the largest ball contained in the stability region centered at the given length vector (the corresponding radius is known as the stability radius). It is well-known that the problems of determining tolerances and the stability radius for the TSP are NP-hard so that in general it is not possible to obtain the above-mentioned three subsets without spending a lot of computation time. The question addressed in this paper is the following: assume that not only an optimal tour is known, but also a set of \(k\) shortest tours \((k\geq 2)\) is given. Then to which extent does this allow us to determine the three subsets in polynomial time? It will be shown in this paper that having \(k\)-best solutions can give the desired information only partially. More precisely, it will be shown that only some of the tolerances can be determined exactly and for the other ones as well as for the stability radius only lower and/or upper bounds can be derived. Since the amount of information that can be derived from the set of \(k\)-best solutions is dependent on both the value of \(k\) as well as on the specific length vector, we present numerical experiments on instances from the TSPLIB library to analyze the effectiveness of our approach.

MSC:

90C35 Programming involving graphs or networks

Software:

TSPLIB
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Chakravarti, N.; Wagelmans, A. P.M., Calculation of stability radii for combinatorial optimization problems, (Econometric Institute Report 9740/A (1997), Erasmus University Rotterdam) · Zbl 0954.90037
[2] (Gal, T.; Greenberg, H. J., Advances in Sensitivity Analysis and Parametric Programming (1997), Kluwer: Kluwer Boston, MA) · Zbl 0881.00025
[3] Geoffrion, A. M.; Nauss, R., Parametric and post-optimality analysis in integer programming, Management Sci., 23, 453-466 (1977) · Zbl 0358.90041
[4] P.C. Gilmore, E.L. Lawler, D.B. Shmoys, Well-solved special cases, Chap. 4 in [11].; P.C. Gilmore, E.L. Lawler, D.B. Shmoys, Well-solved special cases, Chap. 4 in [11]. · Zbl 0631.90081
[5] Greenberg, H. J., An annotated bibliography for post-solution analysis in mixed integer programming and combinatorial optimization, (Internal Report of the Mathematics Department (1997), University of Colorado: University of Colorado Denver) · Zbl 0914.90204
[6] Jenkins, L., Parametric methods in integer linear programming, Ann. Oper. Res., 27, 77-96 (1990) · Zbl 0718.90088
[7] D.S. Johnson, C.H. Papadimitriou, Performance guarantees for heuristics, in: Chap. 5, in Ref. [11].; D.S. Johnson, C.H. Papadimitriou, Performance guarantees for heuristics, in: Chap. 5, in Ref. [11].
[8] Jones, C. V., The stability of solutions to the Euclidean traveling salesman problem: Part I: Experimental results, (Technical Report (1997), School of Business Administration, University of Washington: School of Business Administration, University of Washington Seattle), WA 98195
[9] Jones, C. V., The stability of solutions to the Euclidean traveling salesman problem: Part II: Theoretical results, (Technical Report (1997), School of Business Administration, University of Washington: School of Business Administration, University of Washington Seattle), WA 98195
[10] Kravchenko, S. A.; Sotskov, Y. N.; Werner, F., Optimal schedules with infinitely large stability radius, Optimization, 33, 271-280 (1995) · Zbl 0821.90067
[11] (Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. Rinnooy; Shmoys, D. B., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985), Wiley: Wiley Chichester, New York) · Zbl 0562.00014
[12] Leontev, V. K., Stability of the traveling salesman problem (in Russian), Zurnal Wyczislitielnoj Matiematiki i Matiematiczeskj Fiziki, 15, 1298-1309 (1975)
[13] Libura, M., Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems, Discrete Appl. Math., 30, 197-211 (1991) · Zbl 0718.90091
[14] Padberg, M. W.; Grötschel, M., Polyhedral Theory, (Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. Rinnooy; Shmoys, D. B., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985), Wiley: Wiley Chichester, New York), Ch. 8 · Zbl 0587.90073
[15] Piper, C. J.; Zoltners, A. A., Some easy postoptimality analysis for zero-one programming, Management Sci., 22, 759-765 (1976) · Zbl 0325.90048
[16] Ramaswamy, R.; Chakravarti, N., Complexity of determining exact tolerances for min-sum and min-max combinatorial optimization problems, (Working Paper, Report No. WPS-247/95 (1995), Indian Institute of Management: Indian Institute of Management Calcutta)
[17] Reinelt, G., TSPLIB, A traveling salesman problem library, ORSA J. Comput., 3, 376-384 (1991) · Zbl 0775.90293
[18] Rockafellar, R. T., Convex Analysis (1970), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0229.90020
[19] Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley: Wiley New York · Zbl 0665.90063
[20] Sotskov, Y. N.; Leontev, V. K.; Gordeev, E. N., Some concepts of stability analysis in combinatorial optimization, Discrete Appl. Math., 58, 169-190 (1995) · Zbl 0833.90098
[21] Sotskov, Y. N.; Tanaev, V. S.; Werner, F., Stability radius of an optimal schedule: a survey and recent developments, (Yu, G., Industrial Applications of Combinatorial Optimization (1997), Kluwer Academic Press: Kluwer Academic Press Boston, MA) · Zbl 0936.90030
[22] Sotskov, Y. N.; Wagelmans, A. P.M.; Werner, F., On the calculation of the stability radius of an optimal or an approximate schedule, (Technical Report 9718/A (1997), Econometric Institute, Erasmus University Rotterdam)
[23] van Hoesel, C. P.M.; Wagelmans, A. P.M., On the complexity of postoptimality analysis for 0/1 programs, (Technical Report 9167/A (1991), Erasmus University Rotterdam) · Zbl 0851.90058
[24] van der Poort, E. S.; Libura, M.; Sierksma, G.; van der Veen, J. A.A., Solving the \(k\)-best traveling salesman problem, (Research Report 97A16 (1997), Graduate School/Research Institute Systems, Organizations and Management, University of Groningen) · Zbl 0940.90069
[25] van der Poort, E. S., Aspects of sensitivity analysis for the traveling salesman problem, (Ph.D. Thesis (1997), University of Groningen)
[26] van der Poort, E. S.; Sierksma, G.; van der Veen, J. A.A., Determining tolerances for the traveling salesman problem, (Research Report 97A27 (1997), Graduate School/Research Institute Systems, Organizations and Management, University of Groningen)
[27] van der Poort, E. S.; Dimitrijević, V.; Sierksma, G.; van der Veen, J. A.A., Using stability information for solving the \(k\)-best traveling salesman problem, (Research Report 97A28 (1997), Graduate School/Research Institute Systems, Organizations and Management, University of Groningen)
[28] Volgenant, A.; Jonker, R., A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, European J. Oper. Res., 9, 83-89 (1982) · Zbl 0471.90088
[29] Ward, J. E.; Wendell, R. E., Approaches to sensitivity analysis in linear programming, Ann. Oper. Res., 27, 3-38 (1990) · Zbl 0722.90075
[30] Wendell, R. E., A preview of a tolerance approach to sensitivity in linear programming, Discrete Math., 38, 121-124 (1982) · Zbl 0498.90052
[31] Wendell, R. E., Using bounds on the data in linear programming: the tolerance approach to sensitivity analysis, Math. Programming, 28, 304-322 (1984) · Zbl 0547.90089
[32] Wendell, R. E., The tolerance approach to sensitivity analysis in linear programming, Management Sci., 31, 5, 564-578 (1985) · Zbl 0622.90081
[33] Wilson, G. R.; Jain, H. K., An approach to postoptimality and sensitivity analysis of zero-one goal programs, Naval Res. Logist., 35, 73-84 (1988) · Zbl 0645.90055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.