A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem

DOI10.1016/S0377-2217(00)00143-0zbMath1055.90084OpenAlexW2052035035WikidataQ58024614 ScholiaQ58024614MaRDI QIDQ5939585

Cristina Requejo, Luís Gouveia

Publication date: 2001

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(00)00143-0

zbMATH Keywords

Lagrangean relaxationcentralized telecommunication networksDesign of centralized networksHop constraintslinear programming relaxationminimum spanning treeMulticommodity flowsQuality of service constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (20)

Layered graph approaches for combinatorial optimization problems ⋮ Hop constrained Steiner trees with multiple root nodes ⋮ On the bounded-hop MST problem on random Euclidean instances ⋮ Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem ⋮ Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem ⋮ The network design problem with relays ⋮ A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks ⋮ A hop constrained min-sum arborescence with outage costs ⋮ Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem ⋮ Optimal Hop-Constrained Trees for Nonlinear Cost Flow Networks ⋮ 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 \(k\) edge-disjoint 3-hop-constrained paths polytope ⋮ Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs ⋮ Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints ⋮ New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints ⋮ The hop-constrained minimum cost flow spanning tree problem with nonlinear costs: an ant colony optimization approach ⋮ Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints ⋮ Minimax flow tree problems ⋮ Network design for time‐constrained delivery

Cites Work

• Unnamed Item
• Unnamed Item
• Multicommodity flow models for spanning trees with hop constraints
• The 2-hop spanning tree problem
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Packet Routing in Telecommunication Networks with Path and Flow Restrictions
• Validation of subgradient optimization
• An algorithm for the steiner problem in graphs
• Bundle-based relaxation methods for multicommodity capacitated fixed charge network design

This page was built for publication: A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem