Branch-and-cut and hybrid local search for themulti-level capacitated minimum spanning tree problem.

Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2017-01-23T10:58:14Z No. of bitstreams: 1 ARTIGO_BranchCutHybrid.pdf: 132559 bytes, checksum: c7b12c8b7e63d93e7f01b006f33ef04c (MD5)Approved for entry into archive by Oliveira Flávia (flavia@sisbin.ufop.br) on 2017-01-23T10:59:34Z (GMT) No. of bitstreams: 1 ARTIGO_BranchCutHybrid.pdf: 132559 bytes, checksum: c7b12c8b7e63d93e7f01b006f33ef04c (MD5)Made available in DSpace on 2017-02-01T12:59:05Z (GMT). No. of bitstreams: 1 ARTIGO_BranchCutHybrid.pdf: 132559 bytes, checksum: c7b12c8b7e63d93e7f01b006f33ef04c (MD5) Previous issue date: 2012We propose algorithms to compute tight lower boundsand high quality upper bounds (UBs) for the multilevelcapacitated minimum spanning tree problem. We firstdevelop a branch-and-cut algorithm, introducing somenew features: (i) the exact separation of cuts correspond-ing to some master equality polyhedra found in theformulation; (ii) the separation of Fenchel cuts, solvingLPs considering all the possible solutions restricted tosmall portions of the graph. We then use that branch-and-cut within a GRASP that performs moves by solvingto optimality subproblems corresponding to partial solu-tions. The computational experiments were conductedon 450 benchmark instances from the literature. Numer-ical results show improved best known (UBs) for almostall instances that could not be solved to optimality