Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs

DOI10.1007/S10107-009-0297-2zbMath1218.90201OpenAlexW2100344930MaRDI QIDQ5892561

Luidi Simonetti, Eduardo Uchoa, Luís Gouveia

Publication date: 17 June 2011

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

Full work available at URL: https://doi.org/10.1007/s10107-009-0297-2

zbMATH Keywords

cutting planesinteger programming: formulationstree algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (43)

Layered graph approaches for combinatorial optimization problems ⋮ Hop constrained Steiner trees with multiple root nodes ⋮ Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem ⋮ Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem ⋮ A new approach for the multiobjective minimum spanning tree ⋮ Branch-and-cut methods for the network design problem with vulnerability constraints ⋮ Load-dependent and precedence-based models for pickup and delivery problems ⋮ Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem ⋮ Stabilizing branch‐and‐price for constrained tree problems ⋮ Hop‐level flow formulation for the survivable network design with hop constraints problem ⋮ Extended formulation for hop constrained distribution network configuration problems ⋮ Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem ⋮ A comparison of node‐based and arc‐based hop‐indexed formulations for the Steiner tree problem with hop constraints ⋮ Graph fragmentation problem: analysis and synthesis ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem ⋮ A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints ⋮ A polyhedral study of the diameter constrained minimum spanning tree problem ⋮ On solving bi-objective constrained minimum spanning tree problems ⋮ New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints ⋮ The time dependent traveling salesman problem: polyhedra and algorithm ⋮ Characterizing acyclic graphs by labeling edges ⋮ Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs ⋮ Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs ⋮ A Lagrangean-based decomposition approach for the link constrained Steiner tree problem ⋮ Natural and extended formulations for the time-dependent traveling salesman problem ⋮ The Steiner tree problem with delays: a compact formulation and reduction procedures ⋮ A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems ⋮ Identification of unidentified equality constraints for integer programming problems ⋮ New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints ⋮ Unnamed Item ⋮ A distributed dual ascent algorithm for the Hop-constrained Steiner tree problem ⋮ The hop-constrained minimum cost flow spanning tree problem with nonlinear costs: an ant colony optimization approach ⋮ Reformulations and solution algorithms for the maximum leaf spanning tree problem ⋮ Layered graphs: applications and algorithms ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ Distance Transformation for Network Design Problems ⋮ Upper and lower bounding procedures for the minimum caterpillar spanning problem ⋮ A New Formulation for Spanning Trees ⋮ An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem ⋮ The two-level diameter constrained spanning tree problem ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Design and dimensioning of hydrogen transmission pipeline networks

Uses Software

• SteinLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An intersecting tree model for odd-diameter-constrained minimum spanning and Steiner trees
• The Steiner tree problem
• Multicommodity flow models for spanning trees with hop constraints
• The 2-hop spanning tree problem
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• Notes on polyhedra associated with hop-constrained paths
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs
• A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees
• A dual ascent approach for steiner tree problems on a directed graph
• Constraint Programming for the Diameter Constrained Minimum Spanning Tree Problem
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Solving Steiner tree problems in graphs to optimality
• Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
• Design of Survivable Networks: A survey
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem

This page was built for publication: Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs