Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
From MaRDI portal
Publication:1919978
DOI10.1016/0305-0548(94)00074-IzbMath0854.90139MaRDI QIDQ1919978
Publication date: 19 January 1997
Published in: Computers \& Operations Research (Search for Journal in Brave)
Lagrangean relaxationliftingssubgradient optimizationsubtour eliminationHop constrained minimal spanning tree
Related Items (46)
Hop constrained Steiner trees with multiple root nodes ⋮ Finding bounded diameter minimum spanning tree in general graphs ⋮ On the bounded-hop MST problem on random Euclidean instances ⋮ Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem ⋮ Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations ⋮ 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 ⋮ A hop constrained min-sum arborescence with outage costs ⋮ Lower and upper bounds for the spanning tree with minimum branch vertices ⋮ A branch-and-cut algorithm for the Steiner tree problem with delays ⋮ A voltage drop limited decentralized electric power distribution network ⋮ The profit-oriented hub line location problem with elastic demand ⋮ Two dependency constrained spanning tree problems ⋮ 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 ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ A cost allocation rule for \(k\)-hop minimum cost spanning tree problems ⋮ A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks ⋮ Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs ⋮ 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 ⋮ Ordered weighted average optimization in multiobjective spanning tree problem ⋮ Clustering data that are graph connected ⋮ 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 ⋮ MIP models for connected facility location: a theoretical and computational study ⋮ The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints ⋮ Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints ⋮ The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation ⋮ Minimax flow tree problems ⋮ Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints ⋮ Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? ⋮ A new rule for source connection problems ⋮ The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints ⋮ A model for the capacitated, hop-constrained, per-packet wireless mesh network design problem ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ A branch-and-price procedure for clustering data that are graph connected ⋮ Multicommodity flow models for spanning trees with hop constraints ⋮ The tree of hubs location problem ⋮ Designing reliable tree networks with two cable technologies ⋮ Network design for time‐constrained delivery ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Reducing the diameter of a unit disk graph via node addition
Cites Work
- Unnamed Item
- Unnamed Item
- Integer programming formulations for the multi-depot vehicle routing problem: Comments on a paper by Kulkarni and Bhave
- Edge exchanges in the degree-constrained minimum spanning tree problem
- Multicommodity flow models for spanning trees with hop constraints
- Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
- Integer Programming Formulation of Traveling Salesman Problems
- An Algorithmic Approach to Network Location Problems. II: Thep-Medians
- Topological design of centralized computer networks—formulations and algorithms
- Validation of subgradient optimization
- A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
- Optimum branchings
This page was built for publication: Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
