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

DOI10.1002/net.20307zbMath1203.90129OpenAlexW4250280589MaRDI 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 inequalitiesbranch-and-cutprize collecting traveling salesman problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A branch-and-cut framework for the consistent traveling salesman problem, The orienteering problem with variable profits, A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings, The vehicle routing problem with service level constraints, Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems, FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM, Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem, Hybrid genetic algorithm for undirected traveling salesman problems with profits, Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio, On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms, A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery

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