A branch-and-cut algorithm for the maximum covering cycle problem

DOI10.1007/s10479-018-2856-5zbMath1435.90119OpenAlexW2797687485WikidataQ129994048 ScholiaQ129994048MaRDI QIDQ2288980

Eduardo Álvarez-Miranda, Markus Sinnl

Publication date: 20 January 2020

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

Full work available at URL: https://doi.org/10.1007/s10479-018-2856-5

zbMATH Keywords

branch-and-cutcovering problemsdomination problemsoptimal cycle problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (3)

Metaheuristics for the distance constrained generalized covering traveling salesman problem ⋮ Exact algorithms for budgeted prize-collecting covering subgraph problems ⋮ Minimum constellation covers: hardness, approximability and polynomial cases

Uses Software

• SteinLib

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Searching for a cycle with maximum coverage in undirected graphs
• Time constrained maximal covering salesman problem with weighted demands and partial coverage
• MIP models for connected facility location: a theoretical and computational study
• The bi-objective covering tour problem
• Domination in graphs with bounded propagation: Algorithms, formulations and hardness results
• Permutation graphs: Connected domination and Steiner trees
• The median tour and maximal covering tour problems: Formulations and heuristics
• Approximation algorithms for the Geometric Covering Salesman Problem
• Thinning out Steiner trees: a node-based model for uniform edge costs
• An algorithmic framework for the exact solution of tree-star problems
• The Generalized Covering Salesman Problem
• Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
• The Covering Tour Problem
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• Solving the Orienteering Problem through Branch-and-Cut
• Solving Steiner tree problems in graphs to optimality
• A node‐based ILP formulation for the node‐weighted dominating Steiner problem
• The Covering Salesman Problem
• The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope on a Directed Graph
• Solution of a Large-Scale Traveling-Salesman Problem

This page was built for publication: A branch-and-cut algorithm for the maximum covering cycle problem