Aarhus University Seal / Aarhus Universitets segl

Robust branch-cut-and-price for the Capacitated Minimum Spanning Tree problem over a large extended formulation

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Eduardo Uchoa, Departamento de Engenharia de Produçao, Universidade Federal Fluminense, Niterói, Brazil
  • Ricardo Fukasawa, H. Milton Stewart School of Industrial and Systems Engineering, GeorgiaTech, Atlanta, GA, United States
  • Jens Lysgaard
  • Artur Pessoa, Departamento de Engenharia de Produçao, Universidade Federal Fluminense, Niterói, Brazil
  • Marcus Poggi de Aragão, Departamento de Informática, PUC Rio de Janeiro, Rio de Janerio, Brazil
  • Diego Andrade, RUTCOR, Rutgers University, Piscataway, NJ, United States
  • Department of Business Studies
  • CORAL - Centre for Operations Research Applications in Logistics
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 arborescence 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 are 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 significant improvements over previous algorithms. Several open instances could be solved to optimality.
Original languageEnglish
JournalMathematical Programming
Volume112
Issue2
Pages (from-to)443-472
ISSN0025-5610
DOIs
Publication statusPublished - 2008

See relations at Aarhus University Citationformats

ID: 15464