A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem

DOI10.1002/net.20307zbMath1203.90129MaRDI QIDQ3057103

Jean-Yves Potvin, Jean-François Bérubé, Michel Gendreau

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20307

zbMATH Keywords

valid inequalities; branch-and-cut; prize collecting traveling salesman problem

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90C27: Combinatorial optimization

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

The orienteering problem with variable profits, A branch-and-cut framework for the consistent traveling salesman problem, A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery, The vehicle routing problem with service level constraints, Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems, A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings

Uses Software

• TSPLIB
• SCIP
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The selective travelling salesman problem
• Facet identification for the symmetric traveling salesman polytope
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• Strong linear programming relaxations for the orienteering problem
• On the \(0/1\) knapsack polytope
• Branching rules revisited
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• AN ALGORITHM FOR SINGLE CONSTRAINT MAXIMUM COLLECTION PROBLEM
• The prize collecting traveling salesman problem
• TSPLIB—A Traveling Salesman Problem Library
• New Insertion and Postoptimization Procedures for the Traveling Salesman Problem
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Solving the Orienteering Problem through Branch-and-Cut
• The prize collecting traveling salesman problem: II. Polyhedral results