A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem
From MaRDI portal
Publication:3057103
DOI10.1002/net.20307zbMath1203.90129MaRDI QIDQ3057103
Michel Gendreau, Jean-Yves Potvin, Jean-François Bérubé
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
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 algorithm for the location-routing problem with simultaneous pickup and delivery
Uses Software
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