Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/18420
Title: A feasibility pump and a local branching heuristics for the weight-constrained minimum spanning tree problem
Author: Requejo, Cristina
Santos, Eulália
Keywords: Weighted MST
Minimum spanning tree
Feasibility Pump
Heuristics
Local Branching
Issue Date: 2017
Publisher: Springer International Publishing
Abstract: The Weight-constrained Minimum Spanning Tree problem (WMST) is a combinatorial optimization problem aiming to find a spanning tree of minimum cost with total edge weight not exceeding a given specified limit. This problem has important applications in the telecommunications network design and communication networks. In order to obtain optimal or near optimal solutions to the WMST problem we use heuristic methods based on formulations for finding feasible solutions. The feasibility pump heuristic starts with the LP solution, iteratively fixes the values of some variables and solves the corresponding LP problem until a feasible solution is achieved. In the local branching heuristic a feasible solution is improved by using a local search scheme in which the solution space is reduced to the neighborhood of a feasible solution that is explored for a better feasible solution. Extensive computational results show that these heuristics are quite effective in finding feasible solutions and present small gap values. Each heuristic can be used independently, however the best results were obtained when they are used together and the feasible solution obtained by the feasibility pump heuristic is improved by the local branching heuristic.
URI: http://hdl.handle.net/10773/18420
DOI: 10.1007/978-3-319-62395-5_46
ISBN: 978-3-319-62394-8
ISSN: 0302-9743
Appears in Collections:CIDMA - Capítulo de livro
OGTCG - Capítulo de livro

Files in This Item:
File Description SizeFormat 
WMST-FP+LB-posprint.pdfpost print doc341.55 kBAdobe PDF    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.