On solving cycle problems with Branch-and-Cut: extending shrinking and exact subcycle elimination separation algorithms
Annals of Operations Research 305 : 107-136 (2021)
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.