On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms

DOI10.1007/s10479-021-04210-0zbMath1473.05148arXiv2004.14574OpenAlexW3189193530MaRDI QIDQ2241575

Gorka Kobeaga, María Merino, José A. Lozano

Publication date: 9 November 2021

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.14574

zbMATH Keywords

branch-and-cutexact separationshrinkingcycle problemGomory-Hu treesubcycle elimination

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Paths and cycles (05C38)

Related Items (2)

Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems ⋮ A revisited branch-and-cut algorithm for large-scale orienteering problems

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Solution of large-scale symmetric travelling salesman problems
• Facet identification for the symmetric traveling salesman polytope
• An efficient algorithm for the minimum capacity cut problem
• An analytical comparison of different formulations of the travelling salesman problem
• Practical performance of efficient minimum cut algorithms
• A branch-and-cut algorithm for the capacitated profitable tour problem
• Generating subtour elimination constraints for the TSP from pure integer solutions
• The traveling salesman problem and its variations.
• Cut Tree Algorithms: An Experimental Study
• On the symmetric travelling salesman problem I: Inequalities
• A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem
• Very Simple Methods for All Pairs Network Flow Analysis
• A new approach to the maximum-flow problem
• Multi-Terminal Network Flows
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• TSPLIB—A Traveling Salesman Problem Library
• The Circuit Polytope: Facets
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• Solving the Orienteering Problem through Branch-and-Cut
• The symmetric generalized traveling salesman polytope
• On cycle cones and polyhedra
• A branch and cut approach to the cardinality constrained circuit problem.

This page was built for publication: On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms