A Branch-and-Cut Algorithm for the Undirected Prize Collecting Traveling Salesman Problem

Given an undirected graph with edge costs and vertex prizes, the aim of the Prize Collecting Traveling Salesman Problem (PCTSP) is to find a simple cycle minimizing the total edge cost while collecting at least a minimum amount of prizes. In this article, we present a branch-and-cut algorithm to solve the PCTSP. We have adapted and implemented some classical polyhedral results for the PCTSP and derived inequalities from cuts designed for the Orienteering Problem. Computational results on instances with more than 500 vertices are reported. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 54(1), 56-67 2009