Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs

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 or in the design of telephone networks. 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 flow-based model and which are implied by the compact multicommodity reformulation. Finally, computational results are presented.