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.

--

Capacitated trees,Single and multicommodity flow models,Valid inequalities,Subset sum problems

• Economia e Gestão - Ciências Sociais