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

Eduardo Uchoa (uchoaproducao.uff.br)
Ricardo Fukasawa (rfukasawisye.gatech.edu)
Jens Lysgaard (lysasb.dk)
Artur Pessoa (arturproducao.uff.br)
Marcus Poggi de Aragão (poggiinf.puc-rio.br)
Diogo Andrade (dandraderutcor.rutgers.edu)

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 arborescence probem 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 significant improvements over previous algorithms. Several open instances could be solved to optimality.

Keywords: column generation, cutting planes, extended formulations

Category 1: Integer Programming (Cutting Plane Approaches )

Citation: Technical Report RPEP Vol.6 no.9, Universidade Federal Fluminense, Engenharia de Producao, Niteroi, Brazil.

Download: [PDF]

Entry Submitted: 05/30/2006
Entry Accepted: 05/30/2006
Entry Last Modified: 05/30/2006

Modify/Update this entry