Exportar Publicação

Gouveia, L. & Lopes, M. J. (2000). Valid inequalities for non-unit demand capacitated spanning tree problem with flow costs. European Journal of Operational Research . 121 (2), 394-411

L. Gouveia and M. J. Lopes,  "Valid inequalities for non-unit demand capacitated spanning tree problem with flow costs", in European Journal of Operational Research , vol. 121, no. 2, pp. 394-411, 2000

@article{gouveia2000_1732205977088,
	author = "Gouveia, L. and Lopes, M. J.",
	title = "Valid inequalities for non-unit demand capacitated spanning tree problem with flow costs",
	journal = "European Journal of Operational Research ",
	year = "2000",
	volume = "121",
	number = "2",
	doi = "10.1016/S0377-2217(99)00043-0",
	pages = "394-411",
	url = "https://www.sciencedirect.com/science/article/pii/S0377221799000430?via%3Dihub"
}

TY  - JOUR
TI  - Valid inequalities for non-unit demand capacitated spanning tree problem with flow costs
T2  - European Journal of Operational Research 
VL  - 121
IS  - 2
AU  - Gouveia, L.
AU  - Lopes, M. J.
PY  - 2000
SP  - 394-411
SN  - 0377-2217
DO  - 10.1016/S0377-2217(99)00043-0
UR  - https://www.sciencedirect.com/science/article/pii/S0377221799000430?via%3Dihub
AB  - 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.
ER  -