The capacitated minimum spanning tree problem: On improved multistar constraints

DOI10.1016/j.ejor.2003.10.021zbMath1067.90141OpenAlexW2031476167MaRDI QIDQ1887863

Maria João Lopes, Luís 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)

Related Items

A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem, A biased random-key genetic algorithm for the capacitated minimum spanning tree problem, A Branch-and-Bound Algorithm for Building Optimal Data Gathering Tree in Wireless Sensor Networks, Precedence-constrained arborescences, A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem, Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation, A model for the capacitated, hop-constrained, per-packet wireless mesh network design problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamic programming based heuristics for the topological design of local access networks
• Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs
• The complexity of the capacitated tree problem
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• Validation of subgradient optimization
• Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem
• Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem