Scientific journal paper Q1
Valid inequalities for non-unit demand capacitated spanning tree problem with flow costs
Luís Gouveia (Gouveia, L.); Maria João Lopes (Lopes, M. J.);
Journal Title
European Journal of Operational Research
Year (definitive publication)
2000
Language
English
Country
Netherlands
More Information
Web of Science®

Times Cited: 6

(Last checked: 2024-10-31 20:57)

View record in Web of Science®


: 0.1
Scopus

Times Cited: 6

(Last checked: 2024-10-25 11:52)

View record in Scopus


: 0.1
Google Scholar

Times Cited: 10

(Last checked: 2024-10-31 17:22)

View record in Google Scholar

Abstract
We discuss valid inequalities for a variation of the capacitated minimum spanning tree problem which considers variable flow costs. This variation with flow costs arises in the design of low voltage electricity distribution networks (see Bousba, C., Wolsey, L., 1991. Annals of Operations Research 33, 285-303) or in the design of telephone networks (see Balakrishnan, A., Magnanti, T., Wong, R., 1995. Operations Research, 43, 58-76). We start by pointing out that most of the ideas discussed in the past for the unit-demand versions of the problem are hardly applied to versions with general demands on the nodes. Then, in the context of a flow-based model we propose some valid inequalities for the problem which are based on the optimal solution of an adequate subset sum problem and which "make sense" only when the node demands are different. We also consider a multicommodity reformulation of the original model and adapt for this model the inequalities proposed for the single-commodity flow models. We present an exponentially sized set of lower bounding constraints which are valid for the original how-based model and which are implied by the compact multicommodity reformulation. Finally, computational results are presented.
Acknowledgements
--
Keywords
Capacitated trees,Single and multicommodity flow models,Valid inequalities,Subset sum problems
  • Economics and Business - Social Sciences