The Steiner tree problem with delays: a compact formulation and reduction procedures

DOI10.1016/j.dam.2011.07.008zbMath1323.90074OpenAlexW2146853131MaRDI QIDQ496653

Chefi Triki, Valeria Leggieri, Mohamed Haouari

Publication date: 22 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.07.008

zbMATH Keywords

Steiner tree problemreduction techniquesMTZ subtour elimination constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

An Exact Algorithm for the Steiner Tree Problem with Delays ⋮ Optimal Steiner trees under node and edge privacy conflicts ⋮ A branch-and-cut algorithm for the Steiner tree problem with delays ⋮ Multicast routing under quality of service constraints for vehicular ad hoc networks: mathematical formulation and a relax‐and‐fix heuristic ⋮ New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems ⋮ Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems ⋮ An Algorithm to Find the Link Constrained Steiner Tree in Undirected Graphs ⋮ Multicast problems in telecommunication networks

Uses Software

• SteinLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multicommodity flow models for spanning trees with hop constraints
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• A distributed dual ascent algorithm for the Hop-constrained Steiner tree problem
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Modeling and solving the rooted distance-constrained minimum spanning tree problem
• A survey of combinatorial optimization problems in multicast routing
• The shortest route problem with constraints
• Integer Programming Formulation of Traveling Salesman Problems
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• Problem reduction methods and a tree generation algorithm for the steiner network problem
• A dual algorithm for the constrained shortest path problem
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• Solving Steiner tree problems in graphs to optimality
• Preprocessing Steiner problems from VLSI layout
• 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
• A comparison of Steiner tree relaxations
• Steiner tree problems

This page was built for publication: The Steiner tree problem with delays: a compact formulation and reduction procedures