The capacitated minimum spanning tree problem: On improved multistar constraints

DOI10.1016/J.EJOR.2003.10.021MaRDI QIDQ1887863zbMATH OpenOpenAlexFDO

Authors Maria João Lopes, Luis Gouveia

Publication date 22 November 2004

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

Full work available at URL https://doi.org/10.1016/j.ejor.2003.10.021

zbMATH Keywords

Lagrangean relaxationValid inequalitiesCapacitated treesMultistar constraintsSubset sum problems

Mathematics Subject Classification ID

Trees (05C05) Combinatorial optimization (90C27)

Recommendations

• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
• The capacitated minimal spanning tree problem: An experiment with a hop-indexed model
• The capacitated minimum spanning tree problem: revisiting hop-indexed formulations
• A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem.
• Heuristics for the multi-level capacitated minimum spanning tree problem

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• scientific article; zbMATH DE number 1420487 (Why is no real title available?)
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Dynamic programming based heuristics for the topological design of local access networks
• Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem
• The complexity of the capacitated tree problem
• Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs
• Validation of subgradient optimization

Cited in

(18)

• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• A branch and bound algorithm for the capacitated minimum spanning tree problem
• A simple enhancement of the Esau–Williams heuristic for the capacitated minimum spanning tree problem
• Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem
• A model for the capacitated, hop-constrained, per-packet wireless mesh network design problem
• Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs
• Multistars and directed flow formulations
• Precedence-constrained arborescences
• Parametric enhancements of the Esau–Williams heuristic for the capacitated minimum spanning tree problem
• A biased random-key genetic algorithm for the capacitated minimum spanning tree problem
• GRASP with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem
• The (K,k)-Capacitated Spanning Tree Problem
• A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem
• A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem
• Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem
• The capacitated minimum spanning tree problem: revisiting hop-indexed formulations
• A multicommodity network flow application for the capacitated minimal spanning tree problem
• A branch-and-bound algorithm for building optimal data gathering tree in wireless sensor networks

This page was built for publication: The capacitated minimum spanning tree problem: On improved multistar constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1887863)