Exact algorithms for budgeted prize-collecting covering subgraph problems

DOI10.1016/j.cor.2022.105798OpenAlexW3119998973MaRDI QIDQ2147080

Yanyan Li

Publication date: 22 June 2022

Published in: Computers \& Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

symmetry breakingbranch-and-cutBenders decompositionbudgetcovering problemsprize-collecting problems

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Uses Software

• TSPLIB
• Boost C++ Libraries
• Boost
• stprbh

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Searching for a cycle with maximum coverage in undirected graphs
• Time constrained maximal covering salesman problem with weighted demands and partial coverage
• Branch-and-cut-and-price for capacitated connected facility location
• MIP models for connected facility location: a theoretical and computational study
• The selective travelling salesman problem
• The median tour and maximal covering tour problems: Formulations and heuristics
• The time constrained maximal covering salesman problem
• A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints
• An algorithmic framework for the exact solution of tree-star problems
• A branch-and-cut-and-price approach for the capacitated \(m\)-ring-star problem
• Locating median cycles in networks
• A MIP-based approach to solve the prize-collecting local access network design problem
• A branch-and-cut algorithm for the maximum covering cycle problem
• A cutting plane algorithm for the capacitated connected facility location problem
• Euclidean prize-collecting Steiner forest
• The prize-collecting generalized minimum spanning tree problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems
• Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint
• Survivability in hierarchical telecommunications networks
• A Computational Study of Exact Approaches for the Bi-Objective Prize-Collecting Steiner Tree Problem
• The Capacitated m-Ring-Star Problem
• A New ILP Formulation for 2-Root-Connected Prize-Collecting Steiner Networks
• The node-weighted steiner tree problem
• The prize collecting traveling salesman problem
• TSPLIB—A Traveling Salesman Problem Library
• The Covering Tour Problem
• Solving the Orienteering Problem through Branch-and-Cut
• The Ring Star Problem: Polyhedral analysis and exact algorithm
• The Covering Salesman Problem
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Provisioning a virtual private network
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• The Maximum Weight Connected Subgraph Problem
• Balancing profits and costs on trees
• Uncapacitated and Capacitated Facility Location Problems
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• A Branch and Cut Algorithm for a Steiner Tree-Star Problem

This page was built for publication: Exact algorithms for budgeted prize-collecting covering subgraph problems