Optimization Online


Extended Formulations and Branch-and-Cut Algorithms for the Black-and-White Traveling Salesman Problem

Luis Gouveia(legouveia***at***fc.ul.pt)
Markus Leitner(markus.leitner***at***univie.ac.at)
Mario Ruthmair(mario.ruthmair***at***univie.ac.at)

Abstract: 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 et al., 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 et al., 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.

Keywords: Traveling Salesman Problem; Hop Constraint; Distance Constraint; Integer Linear Programming; Layered Graph; Branch-and-Cut

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Applications -- OR and Management Sciences (Transportation )

Citation: Technical Report, University of Vienna, August, 2016

Download: [PDF]

Entry Submitted: 08/18/2016
Entry Accepted: 08/18/2016
Entry Last Modified: 08/18/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society