Multicommodity flow models for spanning trees with hop constraints
From MaRDI portal
Publication:1278374
DOI10.1016/0377-2217(95)00090-9zbMath0947.90513OpenAlexW2019067222MaRDI QIDQ1278374
Publication date: 22 April 1999
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0377-2217(95)00090-9
integer programmingreliabilitytreesmulticommodity flowslinear programming relaxationshop constraints
Linear programming (90C05) Reliability, availability, maintenance, inspection in operations research (90B25)
Related Items (39)
Greedy heuristics for the diameter-constrained minimum spanning tree problem ⋮ On the bounded-hop MST problem on random Euclidean instances ⋮ Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem ⋮ A biased random-key genetic algorithm for the capacitated minimum spanning tree problem ⋮ Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem ⋮ Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem ⋮ A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks ⋮ Hop‐level flow formulation for the survivable network design with hop constraints problem ⋮ A hop constrained min-sum arborescence with outage costs ⋮ Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints ⋮ A voltage drop limited decentralized electric power distribution network ⋮ A comparison of node‐based and arc‐based hop‐indexed formulations for the Steiner tree problem with hop constraints ⋮ 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 ⋮ A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks ⋮ Unnamed Item ⋮ Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs ⋮ A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints ⋮ Bilinear matrix equation characterizes Laplacian and distance matrices of weighted trees ⋮ The Steiner tree problem with delays: a compact formulation and reduction procedures ⋮ Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem ⋮ New benchmark instances for the capacitated vehicle routing problem ⋮ Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints ⋮ A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem ⋮ New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints ⋮ Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints ⋮ Minimax flow tree problems ⋮ An efficient algorithm for the Steiner tree problem with revenue, bottleneck and hop objective functions ⋮ A model for the capacitated, hop-constrained, per-packet wireless mesh network design problem ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ Distance Transformation for Network Design Problems ⋮ The Minimum Cost Hop-and-root constrained forest in Wireless Sensor Networks ⋮ Stronger column generation bounds for the Minimum Cost Hop-and-root Constrained Forest Problem ⋮ Minimal spanning trees with a constraint on the number of leaves ⋮ Designing reliable tree networks with two cable technologies ⋮ Network design for time‐constrained delivery ⋮ The maximum \(f\)-depth spanning tree problem
Cites Work
- Unnamed Item
- Unnamed Item
- Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
- Using a Hop-Constrained Model to Generate Alternative Communication Network Design
- An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
- Modeling and Heuristic Worst-Case Performance Analysis of the Two-Level Network Design Problem
- A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design
- Validation of subgradient optimization
- A catalog of steiner tree formulations
- Optimum branchings
This page was built for publication: Multicommodity flow models for spanning trees with hop constraints
