The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems | Journal of Global Optimization
Skip to main content
Springer Nature Link
Log in

The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

The tolerance of an element of a combinatorial optimization problem with respect to its optimal solution is the maximum change of the cost of the element while preserving the optimality of the given optimal solution and keeping all other input data unchanged. Tolerances play an important role in the design of exact and approximation algorithms, but the computation of tolerances requires additional computational time. In this paper, we concentrate on combinatorial optimization problems for which the computation of all tolerances and an optimal solution have almost the same computational complexity as of finding an optimal solution only. We summarize efficient computational methods for computing tolerances for these problems and determine their time complexity experimentally.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42–54 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  2. Almoustafa, S., Hanafi, S., Mladenovic, N.: New exact method for large asymmetric distance-constrained vehicle routing problem. Eur. J. Oper. Res. 226, 386–394 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Balas, E., Toth, P.: Branch and bound methods. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.) Chapter 10 of the Traveling Salesman Problem, pp. 361–401. Wiley, Chichester (1985)

    Google Scholar 

  4. Batsyn, M., Goldengorin, B.I., Kocheturov, A., Pardalos, P.M.: Tolerance-based versus cost-based branching for the asymmetric capacitated vehicle routing problem. In: Goldengorin, B.I. et al. (eds.) Models, Algorithms, and Technologies for Network Analysis. Proceedings in Mathematics and Statistics, vol. 59, Springer, Berlin (2013)

  5. Bekker, H., Braad, E.P., Goldengorin, B.: Using bipartite and multidimensional matching to select the roots of a system of polynomial equations. Lect. Notes Comput. Sci. 3483, 397–406 (2005)

    Article  MATH  Google Scholar 

  6. Bekker, H., Braad, E.P., Goldengorin, B.: Selecting the roots of a small system of polynomial equations by tolerance-based matching. Lect. Notes Comput. Sci. 3503, 610–613 (2005)

    Article  MATH  Google Scholar 

  7. Booth, H., Westbrook, J.: A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs. Algorithmica 11, 341–352 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chen, C., Kuo, M., Sheu, J.: An optimal time algorithm for finding a maximum weight independent set in a tree. BIT Numer. Math. 28, 353–356 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  9. Chin, F., Houck, D.: Algorithms for updating minimal spanning trees. J. Comput. Syst. Sci. 16, 333–344 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  10. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Section 24.3: Dijkstra’s Algorithm in Introduction to Algorithms, 2nd edn, pp. 595–601. MIT Press and McGraw Hill, NewYork (2001)

    Google Scholar 

  11. Dell’Amico, M., Toth, P.: Algorithms and codes for dense assignment problems: the state of the art. Discrete Appl. Math. 140, 1–3 (2004)

    Article  MathSciNet  Google Scholar 

  12. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  13. DIMACS, Benchmark instance generates for the ATSP. http://dimacs.rutgers.edu/Challenges/TSP/atsp.html (2006)

  14. Dixon, B., Rauch, M., Tarjan, R.E.: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput. 21(6), 1184–1192 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  15. Fischetti, M., Toth, P., Vigo, D.: A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Oper. Res. 42(5), 846–859 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  16. Fisher, M.L.: The Lagrangian relaxation method for solving integer programming problems. Manag. Sci. 27(1), 1–18 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  17. Germs, R., Goldengorin, B., Turkensteen, M.: Lower tolerance-based branch and bound algorithms for the ATSP. Comput. Oper. Res. 39(2), 291–298 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  18. Ghosh, D., Goldengorin, B., Gutin, G., Jäger, G.: Tolerance-based algorithms for the traveling salesman problem. In: Neogy, S.K., Bapat, R.B., Das, A.K., Parthasarathy, T. (eds.) Mathematical Programming and Game Theory for Decision Making. Statistical Science Interdisciplinary Research, 47–59, World Scientific Publication, Hackensack, NJ (2008)

  19. Ghosh, D., Goldengorin, B., Gutin, G., Jäger, G.: Tolerance-based algorithms for the traveling salesman problem. In: Neogy, S.K., Bapat, R.B., Das, A.K., Parthasarathy, T. (eds.) Chapter of Mathematical Programming and Game Theory for Decision Making, pp. 47–59. World Scientific, New Jersey (2008)

    Chapter  Google Scholar 

  20. Goldengorin, B., Jäger, G., Molitor, P.: Some Basics on Tolerances. In: Cheng, S.-W., Poon, C.K. (eds.) Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM). Lecture Notes in Computer Science 4041, 194–206 (2006)

  21. Goldengorin, B., Jäger, G. Molitor, P.: Tolerance-based Contract-or-Patch Heuristic for the Asymmetric TSP. In: Erlebach, T. (ed.) Proceedinggs 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN). Lecture Notes in Computer Science 4235, 86–97 (2006)

  22. Goldengorin, B., Sierksma, G., Turkensteen, M.: Tolerance-based algorithms for the ATSP. In: Hromkovic, J., Nagl, M., Westfechtel, B. (eds.) Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science 3353, 222–234 (2004)

  23. Goldengorin, B., Sierksma, G.: Combinatorial Optimization Tolerances Calculated in Linear Time. Research Report 03A30, Graduate School/Research Institute Systems, Organizations and Management, University of Groningen, Groningen, The Netherlands (2003)

  24. Goldengorin, B., Malyshev, D.S., Pardalos, P.M.: Efficient computation of tolerances in weighted independent set problems for trees. Dokl. Math. 87(3), 368–371 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  25. Goldengorin, B., Malyshev, D.S., Pardalos, P.M., Zamaraev, V.A.: A tolerance-based heuristic for the weighted independent set problem. J. Comb. Optim. 29, 433–450 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  26. Graham, R.L., Hell, P.: On the history of the minimum spanning tree problem. Ann. Hist. Comput. 7(1), 43–57 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  27. Held, M., Karp, R.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18, 1138–1162 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  28. Helsgaun, K.: An effective implementation of the Lin–Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106–130 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  29. Hillier, F.S., Lieberman, G.J.: Introduction to Operations Research, 6th edn. McGraw Hill, Singapore (1995)

    MATH  Google Scholar 

  30. Johnson, D.S., Gutin, G., McGeoch, L.A., Yeo, A., Zhang, W., Zverovich, A.: Experimental analysis of heuristics for the ATSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and its Variations, pp. 445–487. Kluwer Academic Publishers, Berlin (2002)

    Google Scholar 

  31. Jonker, R., Volgenant, A.: Assignment Solver Code. http://www.assignmentproblems.com/LAPJV.htm (1986)

  32. Jonker, R., Volgenant, A.: Improving the Hungarian assignment algorithm. Oper. Res. Lett. 5, 171–175 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  33. Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38, 325–340 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  34. Kindervater, G., Volgenant, A., de Leve, G., van Gijlswijk, V.: On dual solutions of the linear assignment problem. Eur. J. Oper. Res. 19(1), 76–81 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  35. Kruskal, J.B.: On the shortest spanning tree of a graph and the traveling salesman problem. Proc. Am. Soc. 7, 48–50 (1956)

    Article  MATH  Google Scholar 

  36. Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Q. 2, 83–97 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  37. Lin, C.J., Wen, U.P.: Sensitivity analysis of the optimal assignment. Eur. J. Oper. Res. 149(1), 35–46 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  38. Malyshev, D.S., Pardalos, P.M.: Efficient computation of tolerances in the weighted independent set problem for some classes of graphs. Dokl. Math. 89(2), 253–256 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  39. Pettie, S.: Sensitivity analysis of minimum spanning trees in sub-inverse-ackermann time. In: Deng, X., Du, D., (eds.): ISAAC 2005, LNCS 3827 964–973 (2005)

  40. Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49(1), 16–34 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  41. Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Technol. J. 36, 1389–1401 (1957)

    Article  Google Scholar 

  42. Ramaswamy, R., Orlin, J.B., Chakravarti, N.: Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs. Math. Program. Ser. A 102, 355–369 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  43. Reinelt, G.: TSPLIB—a traveling salesman problem library. ORSA J. Comput. 3, 376–384 (1991)

    Article  MATH  Google Scholar 

  44. Reinfeld, N.V., Vogel, W.R.: Mathematical Programming. Prentice-Hall, Englewood Cliffs, NJ (1958)

    Google Scholar 

  45. Richter, D., Goldengorin, B., Jager, G., Molitor, P.: Improving the efficiency of Helsgaun’s Lin–Kernighan heuristic for the symmetric TSP. Lect. Notes Comput. Sci. 4852, 99–111 (2007)

    Article  MATH  Google Scholar 

  46. Salles da Cunha, A., Lucena, A.: Lower and upper bounds for the degree-constrained minimum spanning tree problem. Networks 50(1), 55–66 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  47. Shier, D.R., Witzgall, C.: Arc tolerances in minimum-path and network flow problems. Networks 10, 277–291 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  48. Tarjan, R.E.: Sensitivity analysis of minimum spanning trees and shortest path trees. Inf. Process. Lett. 14(1), 30–33 (1982)

    Article  MathSciNet  Google Scholar 

  49. Toth, P.: Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems. Eur. J. Oper. Res. 125, 222–238 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  50. Tsplib (Website to [44]). http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html

  51. Turkensteen, M., Ghosh, D., Goldengorin, B., Sierksma, G.: Tolerance-based branch and bound algorithms for the ATSP. Eur. J. Oper. Res. 189(3), 775–788 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  52. Volgenant, A.: A Lagrangean approach to the degree-constrained minimum spanning tree problem. Eur. J. Oper. Res. 39, 325–331 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  53. Volgenant, A.: An addendum on sensitivity analysis of the optimal assignment. Eur. J. Oper. Res. 169, 338–339 (2006)

    Article  MATH  Google Scholar 

  54. Volgenant, T., Jonker, R.: The symmetric traveling salesman problem and edge exchanges in minimal 1-trees. Eur. J. Oper. Res. 12, 394–403 (1983)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The research of D.S. Malyshev and P.M. Pardalos is partially supported by LATNA laboratory, National Research University Higher School of Economics. B. Goldengorin’s research is supported by C. Paul Stocker Visiting Professorship provided by the Department of Industrial and Systems Engineering, The Russ College of Engineering, Ohio University, Athens, OH, USA.

Author information

Authors and Affiliations

  1. Aarhus University, Fuglesangs Alle 4, Aarhus V, Denmark

    Marcel Turkensteen

  2. National Research University Higher School of Economics, 25/12 Bolshaya Pecherskaya Ulitsa, Nizhny Novgorod, Russia, 603155

    Dmitry Malyshev

  3. Ohio University, Athens, OH, 45701, USA

    Boris Goldengorin

  4. University of Florida, 401 Weil Hall, P.O. Box 116595, Gainesville, FL, 326116595, USA

    Boris Goldengorin & Panos M. Pardalos

Authors
  1. Marcel Turkensteen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dmitry Malyshev
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Boris Goldengorin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Panos M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marcel Turkensteen.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Turkensteen, M., Malyshev, D., Goldengorin, B. et al. The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems. J Glob Optim 68, 601–622 (2017). https://doi.org/10.1007/s10898-016-0486-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-016-0486-5

Keywords

Search

Navigation