Artigo em revista científica 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.);
Título Revista
European Journal of Operational Research
Ano (publicação definitiva)
2000
Língua
Inglês
País
Países Baixos (Holanda)
Mais Informação
Web of Science®

N.º de citações: 6

(Última verificação: 2024-10-31 20:57)

Ver o registo na Web of Science®


: 0.1
Scopus

N.º de citações: 6

(Última verificação: 2024-10-25 11:52)

Ver o registo na Scopus


: 0.1
Google Scholar

N.º de citações: 10

(Última verificação: 2024-10-31 17:22)

Ver o registo no Google Scholar

Abstract/Resumo
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.
Agradecimentos/Acknowledgements
--
Palavras-chave
Capacitated trees,Single and multicommodity flow models,Valid inequalities,Subset sum problems
  • Economia e Gestão - Ciências Sociais