  


Extended Formulations and BranchandCut Algorithms for the BlackandWhite Traveling Salesman Problem
Luis Gouveia(legouveiafc.ul.pt) Abstract: In this paper we study integer linear programming models and develop branchandcut algorithms to solve the BlackandWhite 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 nontrivial 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 distancedependent reformulations together with corresponding layered graph representations. Branchandcut 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; BranchandCut 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  