Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman Problem

In this paper we study Integer Linear Programming models and develop branch-and-cut algorithms to solve the Black-and-White Traveling Salesman Problem (BWTSP) (Bourgeois, Laporte, & Semet, 2003) which is a variant of the well known Traveling Salesman Problem (TSP). Two strategies to model the BWTSP have been used in the literature. The problem is either modeled on the original graph as TSP using a single set of binary edge variables and with additional non-trivial hop and distance constraints between every pair of black nodes (see Ghiani, Laporte, & Semat, 2006) or as a sequence of constrained paths composed of white nodes connecting pairs of black nodes (see Muter, 2015). In this paper, we study and develop an intermediate approach based on the observation that it is sufficient to guarantee the required distance (and hop) limit of the path from a given black node to the next black node without explicitly stating which one it is. Thus, instead of stating the two constraints (after adding appropriately defined variables) for each pair of black nodes, they are stated for each black node only (that represents the source of each path). Based on this idea we develop several variants of position- and distance-dependent reformulations together with corresponding layered graph representations. Branch-and-cut algorithms are developed for all proposed formulations and empirically compared by an extensive computational study. The obtained results allow us to provide insights into individual advantages and disadvantages of the different models.