Premium
A branch‐and‐cut algorithm for the undirected prize collecting traveling salesman problem
Author(s) -
Bérubé JeanFrançois,
Gendreau Michel,
Potvin JeanYves
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20307
Subject(s) - travelling salesman problem , undirected graph , orienteering , vertex (graph theory) , bottleneck traveling salesman problem , computer science , branch and cut , combinatorics , enhanced data rates for gsm evolution , graph , 2 opt , mathematics , algorithm , traveling purchaser problem , mathematical optimization , linear programming , artificial intelligence
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. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009