Uchoa, Eduardo () (Departamento de Engenharia de Producão) Fukasawa, Ricardo () (School of Industrial and Systems Engineering) Lysgaard, Jens () (Department of Accounting, Aarhus School of Business) Pessoa, Artur () (Departamento de Engenharia de Producão) Poggi de Aragão, Marcus () (Departamento de Informática) Andrade, Diogo () (RUTCOR)
Abstract
This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to q-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arbores- cence problem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. Moreover, a novel feature is introduced in such kind of algorithms. Powerful new cuts expressed over a very large set of variables could be added, without increasing the complexity of the pricing subproblem or the size of the LPs that are actually solved. Computational results on benchmark instances from the OR-Library show very signi¯cant improvements over previous algorithms. Several open instances could be solved to optimality
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by University of Aarhus, Aarhus School of Business, Department of Business Studies in its series CORAL Working Papers with number
L-2006-08.
References listed on IDEAS Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
Did you know? Each page is provided with a technical contact, in case something is not right with the supplied information. See under "publisher info".