Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints

DOI10.1002/net.20274zbMath1180.90348OpenAlexW4245460500MaRDI QIDQ5191136

Alysson M. Costa, Gilbert Laporte, Jean-François Cordeau

Publication date: 28 July 2009

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20274

zbMATH Keywords

network designprize collecting

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph theory (including graph drawing) in computer science (68R10)

Related Items

An Exact Algorithm for the Steiner Tree Problem with Delays, Layered graph approaches for combinatorial optimization problems, Exact algorithms for budgeted prize-collecting covering subgraph problems, Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints, Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem, Branch-and-price approaches for the network design problem with relays, Exact algorithms for bi-objective ring tree problems with reliability measures, A branch-and-cut algorithm for the Steiner tree problem with delays, New formulations and branch-and-cut procedures for the longest induced path problem, MIP formulations for induced graph optimization problems: a tutorial, A comparison of node‐based and arc‐based hop‐indexed formulations for the Steiner tree problem with hop constraints, Maximum weighted induced forests and trees: new formulations and a computational comparative review, A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints, Optimal Network Design with End-to-End Service Requirements, A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks, Sustainable vegetable crop supply problem with perishable stocks, Natural and extended formulations for the time-dependent traveling salesman problem, The Steiner tree problem with delays: a compact formulation and reduction procedures, Breakout local search for the Steiner tree problem with revenue, budget and hop constraints, Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints, MIP models for connected facility location: a theoretical and computational study, Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem, An efficient algorithm for the Steiner tree problem with revenue, bottleneck and hop objective functions, Capacitated ring arborescence problems with profits, Towards optimizing the deployment of optical access networks, An integer linear programming approach for approximate string comparison

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• Facets of two Steiner arborescence polyhedra
• Multicommodity flow models for spanning trees with hop constraints
• The Steiner tree problem with hop constraints
• The Steiner tree polytope and related polyhedra
• Tree polytope on 2-trees
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem. II: Properties and classes of facets
• Strong lower bounds for the prize collecting Steiner problem in graphs
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• The prize-collecting generalized minimum spanning tree problem
• Local search with perturbations for the prize-collecting Steiner tree problem in graphs
• A comparative analysis of several formulations for the generalized minimum spanning tree problem
• Integer Programming Formulation of Traveling Salesman Problems
• The node-weighted steiner tree problem
• The Complexity of Computing Steiner Minimal Trees
• A test problem generator for the Steiner problem in graphs
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Solving Steiner tree problems in graphs to optimality
• Strong formulations for network design problems with connectivity requirements
• A General Approximation Technique for Constrained Forest Problems
• Steiner Minimal Trees
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem