A carregar...
Publicação
Formulations for the Weight-Constrained Minimum Spanning Tree Problem
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 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 |
Orientador(es)
Resumo(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.
Descrição
Conference name - International Conference on Numerical Analysis and Applied Mathematics 2010, ICNAAM-2010; Conference date - 19 September 2010 - 25 September 2010
Palavras-chave
minimum spanning tree weight-constraint extended formulation knapsack constraint
Contexto Educativo
Citação
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.
Editora
American Institute of Physics
Licença CC
Sem licença CC