Formulations for the Weight-Constrained Minimum Spanning Tree Problem

Requejo, Cristina; Agra, Agostinho; Cerveira, Adelaide; Santos, Eulália

http://hdl.handle.net/10400.8/14435

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
Formulations for the weight-constrained minimum spanning tree problem.pdf	We consider the Weight-constrained Minimum Spanning Tree problem (WMST). The WMST aims at finding a minimum spanning tree such that the overall tree weight does not exceed a specified limit on a graph with costs and weights associated with each edge. We present and compare, from the computational point of view, several formulations for the WMST. From preliminary computational results we propose a model that combines a formulation similar to the well known Miller-Tucker-Zemlin formulation with the cut-set inequalities.	130.4 KB	Adobe PDF	Download

Send Feedback

Authors

Abstract(s)

We consider the Weight-constrained Minimum Spanning Tree problem (WMST). The WMST aims at finding a minimum spanning tree such that the overall tree weight does not exceed a specified limit on a graph with costs and weights associated with each edge. We present and compare, from the computational point of view, several formulations for the WMST. From preliminary computational results we propose a model that combines a formulation similar to the well known Miller-Tucker-Zemlin formulation with the cut-set inequalities.

Description

Conference name - International Conference on Numerical Analysis and Applied Mathematics 2010, ICNAAM-2010; Conference date - 19 September 2010 - 25 September 2010

Keywords

minimum spanning tree weight-constraint extended formulation knapsack constraint

URI

http://hdl.handle.net/10400.8/14435

Citation

Cristina Requejo, Agostinho Agra, Adelaide Cerveira, Eulália Santos; Formulations for the Weight‐Constrained Minimum Spanning Tree Problem. AIP Conf. Proc. 30 September 2010; 1281 (1): 2166–2169. https://doi.org/10.1063/1.3498397.