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

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

Luís Gouveia, Cristina Requejo

Publication date: 2001

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

zbMATH Keywords

Lagrangean relaxation; centralized telecommunication networks; Design of centralized networks; Hop constraints; linear programming relaxation; minimum spanning tree; Multicommodity flows; Quality of service constraints

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

Related Items

Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, Network design for time‐constrained delivery, The network design problem with relays, A hop constrained min-sum arborescence with outage costs, On the bounded-hop MST problem on random Euclidean instances, Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints

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