Mostrar el registro sencillo del ítem
On solving cycle problems with Branch-and-Cut: extending shrinking and exact subcycle elimination separation algorithms
dc.contributor.author | Kobeaga Urriolabeitia, Gorka ![]() | |
dc.contributor.author | Merino Maestre, María ![]() | |
dc.contributor.author | Lozano Alonso, José Antonio | |
dc.date.accessioned | 2024-02-08T11:21:28Z | |
dc.date.available | 2024-02-08T11:21:28Z | |
dc.date.issued | 2021-08-03 | |
dc.identifier.citation | Annals of Operations Research 305 : 107-136 (2021) | es_ES |
dc.identifier.issn | 1572-9338 | |
dc.identifier.issn | 0254-5330 | |
dc.identifier.uri | http://hdl.handle.net/10810/65549 | |
dc.description.abstract | In this paper, we extend techniques developed in the context of the Travelling Salesperson Problem for cycle problems. Particularly, we study the shrinking of support graphs and the exact algorithms for subcycle elimination separation problems. The efficient application of the considered techniques has proved to be essential in the Travelling Salesperson Problem when solving large size problems by Branch-and-Cut, and this has been the motivation behind this work. Regarding the shrinking of support graphs, we prove the validity of the Padberg-Rinaldi general shrinking rules and the Crowder-Padberg subcycle-safe shrinking rules. Concerning the subcycle separation problems, we extend two exact separation algorithms, the Dynamic Hong and the Extended Padberg-Grötschel algorithms, which are shown to be superior to the ones used so far in the literature of cycle problems. The proposed techniques are empirically tested in 24 subcycle elimination problem instances generated by solving the Orienteering Problem (involving up to 15112 vertices) with Branch-and-Cut. The experiments suggest the relevance of the proposed techniques for cycle problems. The obtained average speedup for the subcycle separation problems in the Orienteering Problem when the proposed techniques are used together is around 50 times in medium-sized instances and around 250 times in large-sized instances. | es_ES |
dc.description.sponsorship | G. Kobeaga: supported by the grant BES-2015-072036 (Spanish Ministry of Economy and Competitiveness) and the project ELKARTEK (Basque Government). M. Merino: supported by PID2019-104933GB-I00/AEI/10.13039/501100011033 (Spanish Ministry of Science and Innovation), IT-1252-19 (Basque Government) and GIU20/054 (University of the Basque Country). J. A. Lozano: supported by BERC 2018-2021 and IT1244-19 (Basque Government), SEV-2017-0718 (Spanish Ministry of Economy and Competitiveness) and PID2019-104966GB-I00/AEI/10.13039/501100011033 (Spanish Ministry of Science and Innovation). | es_ES |
dc.language.iso | eng | es_ES |
dc.publisher | Springer | es_ES |
dc.relation | info:eu-repo/grantAgreement//MICIN/PID2019-104933GB-I00 | |
dc.relation | info:eu-repo/grantAgreement/MICIN/PID2019-104966GB-I00 | |
dc.rights | info:eu-repo/semantics/openAccess | es_ES |
dc.subject | cycle problem | es_ES |
dc.subject | branch-and-cut | |
dc.subject | shrinking | |
dc.subject | exact separation | |
dc.subject | subcycle elimination | |
dc.subject | gomory-hu tree | |
dc.title | On solving cycle problems with Branch-and-Cut: extending shrinking and exact subcycle elimination separation algorithms | es_ES |
dc.type | info:eu-repo/semantics/article | es_ES |
dc.rights.holder | © 2021, The Author(s), under exclusive licence to Springer Science Business Media, LLC, part of Springer Nature | * |
dc.relation.publisherversion | https://link.springer.com/article/10.1007/s10479-021-04210-0#citeas | es_ES |
dc.identifier.doi | 10.1007/s10479-021-04210-0 | |
dc.departamentoes | Matemáticas | es_ES |
dc.departamentoeu | Matematika | es_ES |