Robust Branch-Cut-and-Price for the Capacitated Minimum Spanning Tree Problem over a Large Extended Formulation

Eduardo Uchoa (), Ricardo Fukasawa (), Jens Lysgaard, Artur Pessoa (), Marcus Poggi de Aragão () and Diogo Andrade ()
Additional contact information
Eduardo Uchoa: Departamento de Engenharia de Producão, Postal: Universidade Federal Fluminense, Brazil
Ricardo Fukasawa: School of Industrial and Systems Engineering, Postal: GeorgiaTech, USA
Jens Lysgaard: Department of Accounting, Aarhus School of Business, Postal: The Aarhus School of Business, Fuglesangs Allé 4, 8210 Aarhus V, Denmark, http://www.asb.dk/staff/bs/lys.aspx?page=%7B803EFF10-69F7-4C0F-AEE3-F7F410E4B6F2%7D
Artur Pessoa: Departamento de Engenharia de Producão, Postal: Universidade Federal Fluminense, Brazil
Marcus Poggi de Aragão: Departamento de Informática, Postal: PUC, Rio de Janeiro, Brazil
Diogo Andrade: RUTCOR, Postal: Rutgers University, USA

No L-2006-08, CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies

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

Keywords: No keywords (search for similar items in EconPapers)
Pages: 34 pages
Date: 2006-05-01
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.hha.dk/bs/wp/log/L_2006_08.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to www.hha.dk:80 (No such host is known. )

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhb:aarbls:2006-008

Access Statistics for this paper

More papers in CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies The Aarhus School of Business, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Helle Vinbaek Stenholt ( this e-mail address is bad, please contact ).