A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints

DOI10.1007/s12532-016-0102-1zbMath1391.90421DBLPjournals/mpc/SinnlL16OpenAlexW2296679062WikidataQ59471136 ScholiaQ59471136MaRDI QIDQ1694297

Markus Sinnl, Ivana Ljubić

Publication date: 1 February 2018

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-016-0102-1

zbMATH Keywords

mixed integer programmingbranch-and-cutexact computationnode-based modellayered graphhop-constrained trees

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (6)

Layered graph approaches for combinatorial optimization problems ⋮ Exact algorithms for budgeted prize-collecting covering subgraph problems ⋮ Benders decomposition for network design covering problems ⋮ A comparison of node‐based and arc‐based hop‐indexed formulations for the Steiner tree problem with hop constraints ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ stprbh

Uses Software

• SteinLib
• CPLEX
• OGDF
• OR-Library
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Hop constrained Steiner trees with multiple root nodes
• Benders decomposition without separability: a computational study for capacitated facility location problems
• On implementing the push-relabel method for the maximum flow problem
• Thinning out Steiner trees: a node-based model for uniform edge costs
• A polyhedral study of the diameter constrained minimum spanning tree problem
• Breakout local search for the Steiner tree problem with revenue, budget and hop constraints
• The two-level diameter constrained spanning tree problem
• Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints
• Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Acceleration of cutting-plane and column generation algorithms: Applications to network design
• Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints
• An In-Out Approach to Disjunctive Optimization
• Steiner problem in networks: A survey
• Reduction tests for the steiner problem in grapsh
• Solving Steiner tree problems in graphs to optimality
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• Steiner tree problems

This page was built for publication: A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints