Show simple item record

dc.contributor.authorKobeaga, G. 
dc.contributor.authorMerino, M. 
dc.contributor.authorLozano, J.A.
dc.description.abstractIn 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 15,112 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.en_US
dc.description.sponsorshipPID2019-104933GB-I00/AEI/10.13039/501100011033 PID2019-104966GB-I00/AEI/10.13039/501100011033 IT-1252-19 GIU20/054en_US
dc.rightsReconocimiento-NoComercial-CompartirIgual 3.0 Españaen_US
dc.titleOn solving cycle problems with Branch-and-Cut: extending shrinking and exact subcycle elimination separation algorithmsen_US
dc.journal.titleAnnals of Operations Researchen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Reconocimiento-NoComercial-CompartirIgual 3.0 España
Except where otherwise noted, this item's license is described as Reconocimiento-NoComercial-CompartirIgual 3.0 España