Stronger MIP formulations for the Steiner forest problem

DOI10.1007/s10107-019-01460-6zbMath1459.90188OpenAlexW2998253363MaRDI QIDQ2227541

Bernd Zey, Daniel R. Schmidt, Margot, François

Publication date: 15 February 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-019-01460-6

zbMATH Keywords

integer programmingbranch-and-cut algorithmSteiner forest problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem, Distance Transformation for Network Design Problems

Uses Software

• SteinLib
• OGDF

Cites Work

• Unnamed Item
• Unnamed Item
• A factor 2 approximation algorithm for the generalized Steiner network problem
• The Steiner tree problem on graphs: inapproximability results
• The Steiner tree polytope and related polyhedra
• Tree polytope on 2-trees
• Arborescence polytopes for series-parallel graphs
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem. II: Properties and classes of facets
• On implementing the push-relabel method for the maximum flow problem
• Greedy Algorithms for Steiner Forest
• Steiner trees, partial 2–trees, and minimum IFI networks
• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
• A new approach to the maximum-flow problem
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• Solving Steiner tree problems in graphs to optimality
• Strong formulations for network design problems with connectivity requirements
• A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• A Local-Search Algorithm for Steiner Forest
• An Exact Algorithm for the Steiner Forest Problem
• A catalog of steiner tree formulations
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Steiner Tree Approximation via Iterative Randomized Rounding
• A comparison of Steiner tree relaxations