A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems

DOI10.1287/ijoc.2017.0788zbMath1446.90060OpenAlexW2803872014WikidataQ57705346 ScholiaQ57705346MaRDI QIDQ5131733

Martin Luipersbeck, Markus Leitner, Markus Sinnl, Ivana Ljubić

Publication date: 9 November 2020

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/34d6b04cfc96370e562838908201568b17556804

zbMATH Keywords

branch-and-boundSteiner treesdual ascentreduction testsprize-collecting Steiner trees

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Communication networks in operations research (90B18)

Related Items (11)

Layered graph approaches for combinatorial optimization problems ⋮ Combinatorial Heuristics for Inventory Routing Problems ⋮ On the Exact Solution of Prize-Collecting Steiner Tree Problems ⋮ Optimal connected subgraphs: Integer programming formulations and polyhedra ⋮ Heuristic and exact algorithms for minimum-weight non-spanning arborescences ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem ⋮ Vertex covering with capacitated trees ⋮ Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem ⋮ Decomposition methods for the two-stage stochastic Steiner tree problem ⋮ An exact solution framework for the minimum cost dominating tree problem

Uses Software

• SteinLib
• SCIP-Jack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Thinning out Steiner trees: a node-based model for uniform edge costs
• SCIP-Jack -- a solver for STP and variants with parallelization extensions
• Swap-vertex based neighborhood for Steiner tree problems
• Reduction tests for the prize-collecting Steiner problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• A dual ascent approach for steiner tree problems on a directed graph
• Reduction tests for the steiner problem in grapsh
• A note on finding optimum branchings
• A fast algorithm for finding dominators in a flowgraph
• Solving Steiner tree problems in graphs to optimality
• A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design
• A General Approximation Technique for Constrained Forest Problems
• The Maximum Weight Connected Subgraph Problem
• Optimum branchings
• Improved algorithms for the Steiner problem in networks

This page was built for publication: A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems