IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v68y2017i3d10.1007_s10898-016-0486-5.html

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

Author

Listed:
  • Marcel Turkensteen

    (Aarhus University)

  • Dmitry Malyshev

    (National Research University Higher School of Economics)

  • Boris Goldengorin

    (Ohio University
    University of Florida)

  • Panos M. Pardalos

    (University of Florida)

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.

Suggested Citation

  • Marcel Turkensteen & Dmitry Malyshev & Boris Goldengorin & Panos M. Pardalos, 2017. "The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems," Journal of Global Optimization, Springer, vol. 68(3), pages 601-622, July.
    • Handle: RePEc:spr:jglopt:v:68:y:2017:i:3:d:10.1007_s10898-016-0486-5
    DOI: 10.1007/s10898-016-0486-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-016-0486-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-016-0486-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Volgenant, Ton & Jonker, Roy, 1983. "The symmetric traveling salesman problem and edge exchanges in minimal 1-trees," European Journal of Operational Research, Elsevier, vol. 12(4), pages 394-403, April.
    2. Almoustafa, Samira & Hanafi, Said & Mladenović, Nenad, 2013. "New exact method for large asymmetric distance-constrained vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 226(3), pages 386-394.
    3. Marshall L. Fisher, 1981. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 27(1), pages 1-18, January.
    4. Volgenant, A., 1989. "A Lagrangean approach to the degree-constrained minimum spanning tree problem," European Journal of Operational Research, Elsevier, vol. 39(3), pages 325-331, April.
    5. Matteo Fischetti & Paolo Toth & Daniele Vigo, 1994. "A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs," Operations Research, INFORMS, vol. 42(5), pages 846-859, October.
    6. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    7. Michael Held & Richard M. Karp, 1970. "The Traveling-Salesman Problem and Minimum Spanning Trees," Operations Research, INFORMS, vol. 18(6), pages 1138-1162, December.
    8. Lin, Chi-Jen & Wen, Ue-Pyng, 2003. "Sensitivity analysis of the optimal assignment," European Journal of Operational Research, Elsevier, vol. 149(1), pages 35-46, August.
    9. Goldengorin, Boris & Sierksma, Gerard, 2003. "Combinatorial optimization tolerances calculated in linear time," Research Report 03A30, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    10. Toth, Paolo, 2000. "Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 125(2), pages 222-238, September.
    11. repec:dgr:rugsom:03a30 is not listed on IDEAS
    12. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    13. Kindervater, G. & Volgenant, A. & de Leve, G. & van Gijlswijk, V., 1985. "On dual solutions of the linear assignment problem," European Journal of Operational Research, Elsevier, vol. 19(1), pages 76-81, January.
    14. Volgenant, A., 2006. "An addendum on sensitivity analysis of the optimal assignment," European Journal of Operational Research, Elsevier, vol. 169(1), pages 338-339, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Long Wang & Jiongzhi Zheng & Zhengda Xiong & Kun He, 2026. "Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem and its Variants," Journal of Heuristics, Springer, vol. 32(1), pages 1-32, March.
    2. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    3. Toni Pacheco & Rafael Martinelli & Anand Subramanian & Túlio A. M. Toffolo & Thibaut Vidal, 2023. "Exponential-Size Neighborhoods for the Pickup-and-Delivery Traveling Salesman Problem," Transportation Science, INFORMS, vol. 57(2), pages 463-481, March.
    4. Jean-Charles Créput & Amir Hajjam & Abderrafiaa Koukam & Olivier Kuhn, 2012. "Self-organizing maps in population based metaheuristic to the dynamic vehicle routing problem," Journal of Combinatorial Optimization, Springer, vol. 24(4), pages 437-458, November.
    5. A N Letchford & J Lysgaard & R W Eglese, 2007. "A branch-and-cut algorithm for the capacitated open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1642-1651, December.
    6. Mauro Dell’Amico & Roberto Montemanni & Stefano Novellani, 2020. "Matheuristic algorithms for the parallel drone scheduling traveling salesman problem," Annals of Operations Research, Springer, vol. 289(2), pages 211-226, June.
    7. Gary R. Waissi & Pragya Kaushal, 2020. "A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP," OPSEARCH, Springer;Operational Research Society of India, vol. 57(1), pages 73-87, March.
    8. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    9. Lucas García & Pedro M. Talaván & Javier Yáñez, 2022. "The 2-opt behavior of the Hopfield Network applied to the TSP," Operational Research, Springer, vol. 22(2), pages 1127-1155, April.
    10. William Cook & Daniel G. Espinoza & Marcos Goycoolea, 2007. "Computing with Domino-Parity Inequalities for the Traveling Salesman Problem (TSP)," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 356-365, August.
    11. Samuel C. Gutekunst & David P. Williamson, 2023. "The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP," Mathematics of Operations Research, INFORMS, vol. 48(1), pages 393-418, February.
    12. Konstantin Pavlikov & Niels Christian Petersen, 2025. "Two-commodity opposite direction network flow formulations for the travelling salesman problem," Computational Optimization and Applications, Springer, vol. 92(3), pages 987-1033, December.
    13. Bruce Golden & Zahra Naji-Azimi & S. Raghavan & Majid Salari & Paolo Toth, 2012. "The Generalized Covering Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 534-553, November.
    14. K Sang-Ho & G Young-Gun & K Maing-Kyu, 2003. "Application of the out-of-kilter algorithm to the asymmetric traveling salesman problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(10), pages 1085-1092, October.
    15. Shaowen Lan & Yongliang Lu & Wenjuan Fan, 2025. "An adaptive variable neighborhood search for the traveling salesman problem with job-times," Journal of Heuristics, Springer, vol. 31(2), pages 1-65, June.
    16. Jeanette Schmidt & Stefan Irnich, 2020. "New Neighborhoods and an Iterated Local Search Algorithm for the Generalized Traveling Salesman Problem," Working Papers 2020, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    17. Chris Walshaw, 2002. "A Multilevel Approach to the Travelling Salesman Problem," Operations Research, INFORMS, vol. 50(5), pages 862-877, October.
    18. William Cook & Paul Seymour, 2003. "Tour Merging via Branch-Decomposition," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 233-248, August.
    19. L Vogt & C A Poojari & J E Beasley, 2007. "A tabu search algorithm for the single vehicle routing allocation problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(4), pages 467-480, April.
    20. Burger, M. & Su, Z. & De Schutter, B., 2018. "A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 265(2), pages 463-477.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:68:y:2017:i:3:d:10.1007_s10898-016-0486-5. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.