IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v290y2021i1p36-56.html
   My bibliography  Save this article

A comparative analysis of two matheuristics by means of merged local optima networks

Author

Listed:
  • Blum, Christian
  • Ochoa, Gabriela

Abstract

We present a comparative analysis of two hybrid algorithms for solving combinatorial optimisation problems. The first one is a specific variant of an established family of techniques known as large neighbourhood search (LNS). The second one is a much more recent algorithm known as construct, merge, solve & adapt (CMSA). Both approaches generate, in different ways, reduced sub-instances of the tackled problem instance at each iteration. The experimental analysis is conducted on two NP-hard combinatorial subset selection problems: the multidimensional knapsack problem and minimum common string partition. The results support the intuition that CMSA has advantages over the LNS variant in the context of problems for which solutions contain rather few items. Moreover, they show that the opposite may be the case for problems in which solutions contain rather many items. The analysis is supported by a new way of visualising the trajectories of the compared algorithms in terms of merged monotonic local optima networks.

Suggested Citation

  • Blum, Christian & Ochoa, Gabriela, 2021. "A comparative analysis of two matheuristics by means of merged local optima networks," European Journal of Operational Research, Elsevier, vol. 290(1), pages 36-56.
    • Handle: RePEc:eee:ejores:v:290:y:2021:i:1:p:36-56
    DOI: 10.1016/j.ejor.2020.08.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720306998
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.08.008?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 search for a different version of it.

    References listed on IDEAS

    as
    1. Blum, Christian & Lozano, José A. & Davidson, Pinacho, 2015. "Mathematical programming strategies for solving the minimum common string partition problem," European Journal of Operational Research, Elsevier, vol. 242(3), pages 769-777.
    2. Hanafi, Said & Freville, Arnaud, 1998. "An efficient tabu search approach for the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 659-675, April.
    3. Gabriela Ochoa & Nadarajen Veerapen, 2018. "Mapping the global structure of TSP fitness landscapes," Journal of Heuristics, Springer, vol. 24(3), pages 265-294, June.
    4. William Cook & Paul Seymour, 2003. "Tour Merging via Branch-Decomposition," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 233-248, August.
    5. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2012. "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 346-359.
    6. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    7. Schmid, Verena, 2014. "Hybrid large neighborhood search for the bus rapid transit route design problem," European Journal of Operational Research, Elsevier, vol. 238(2), pages 427-437.
    8. López-Ibáñez, Manuel & Dubois-Lacoste, Jérémie & Pérez Cáceres, Leslie & Birattari, Mauro & Stützle, Thomas, 2016. "The irace package: Iterated racing for automatic algorithm configuration," Operations Research Perspectives, Elsevier, vol. 3(C), pages 43-58.
    9. Marco Caserta & Stefan Voß, 2016. "A corridor method based hybrid algorithm for redundancy allocation," Journal of Heuristics, Springer, vol. 22(4), pages 405-429, August.
    10. Guastaroba, G. & Speranza, M.G., 2012. "Kernel Search: An application to the index tracking problem," European Journal of Operational Research, Elsevier, vol. 217(1), pages 54-68.
    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. Alberto Santini & Stefan Ropke & Lars Magnus Hvattum, 2018. "A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic," Journal of Heuristics, Springer, vol. 24(5), pages 783-815, October.
    2. Véronique François & Yasemin Arda & Yves Crama, 2019. "Adaptive Large Neighborhood Search for Multitrip Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 53(6), pages 1706-1730, November.
    3. Pagnozzi, Federico & Stützle, Thomas, 2019. "Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems," European Journal of Operational Research, Elsevier, vol. 276(2), pages 409-421.
    4. Saïd Hanafi & Christophe Wilbaut, 2011. "Improved convergent heuristics for the 0-1 multidimensional knapsack problem," Annals of Operations Research, Springer, vol. 183(1), pages 125-142, March.
    5. Kallestad, Jakob & Hasibi, Ramin & Hemmati, Ahmad & Sörensen, Kenneth, 2023. "A general deep reinforcement learning hyperheuristic framework for solving combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 309(1), pages 446-468.
    6. Swan, Jerry & Adriaensen, Steven & Brownlee, Alexander E.I. & Hammond, Kevin & Johnson, Colin G. & Kheiri, Ahmed & Krawiec, Faustyna & Merelo, J.J. & Minku, Leandro L. & Özcan, Ender & Pappa, Gisele L, 2022. "Metaheuristics “In the Large”," European Journal of Operational Research, Elsevier, vol. 297(2), pages 393-406.
    7. Turkeš, Renata & Sörensen, Kenneth & Hvattum, Lars Magnus, 2021. "Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search," European Journal of Operational Research, Elsevier, vol. 292(2), pages 423-442.
    8. Al-Shihabi, Sameh, 2021. "A Novel Core-Based Optimization Framework for Binary Integer Programs- the Multidemand Multidimesional Knapsack Problem as a Test Problem," Operations Research Perspectives, Elsevier, vol. 8(C).
    9. Wu, Dexiang & Kwon, Roy H. & Costa, Giorgio, 2017. "A constrained cluster-based approach for tracking the S&P 500 index," International Journal of Production Economics, Elsevier, vol. 193(C), pages 222-243.
    10. Hernández-Pérez, Hipólito & Rodríguez-Martín, Inmaculada & Salazar-González, Juan-José, 2016. "A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 251(1), pages 44-52.
    11. Pan, Binbin & Zhang, Zhenzhen & Lim, Andrew, 2021. "Multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 291(1), pages 218-231.
    12. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    13. Asghari, Mohammad & Jaber, Mohamad Y. & Mirzapour Al-e-hashem, S.M.J., 2023. "Coordinating vessel recovery actions: Analysis of disruption management in a liner shipping service," European Journal of Operational Research, Elsevier, vol. 307(2), pages 627-644.
    14. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
    15. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    16. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2018. "Minimizing Piecewise-Concave Functions Over Polyhedra," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 580-597, May.
    17. Amina Lamghari & Roussos Dimitrakopoulos & Jacques Ferland, 2015. "A hybrid method based on linear programming and variable neighborhood descent for scheduling production in open-pit mines," Journal of Global Optimization, Springer, vol. 63(3), pages 555-582, November.
    18. Patricia Domínguez-Marín & Stefan Nickel & Pierre Hansen & Nenad Mladenović, 2005. "Heuristic Procedures for Solving the Discrete Ordered Median Problem," Annals of Operations Research, Springer, vol. 136(1), pages 145-173, April.
    19. Ali Shahabi & Sadigh Raissi & Kaveh Khalili-Damghani & Meysam Rafei, 2021. "Designing a resilient skip-stop schedule in rapid rail transit using a simulation-based optimization methodology," Operational Research, Springer, vol. 21(3), pages 1691-1721, September.
    20. Wilson, Duncan T. & Hawe, Glenn I. & Coates, Graham & Crouch, Roger S., 2013. "A multi-objective combinatorial model of casualty processing in major incident response," European Journal of Operational Research, Elsevier, vol. 230(3), pages 643-655.

    More about this item

    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:eee:ejores:v:290:y:2021:i:1:p:36-56. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.