Premium
Branch‐and‐cut and hybrid local search for the multi‐level capacitated minimum spanning tree problem
Author(s) -
Uchoa Eduardo,
Toffolo Túlio A. M.,
de Souza Mauricio C.,
Martins Alexandre X.,
Fukasawa Ricardo
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20485
Subject(s) - minimum spanning tree , spanning tree , grasp , benchmark (surveying) , mathematical optimization , branch and cut , branch and bound , polyhedron , mathematics , tree (set theory) , computer science , cutting plane method , combinatorics , linear programming , integer programming , geodesy , programming language , geography
We propose algorithms to compute tight lower bounds and high quality upper bounds (UBs) for the multilevel capacitated minimum spanning tree problem. We first develop a branch‐and‐cut algorithm, introducing some new features: (i) the exact separation of cuts corresponding to some master equality polyhedra found in the formulation; (ii) the separation of Fenchel cuts, solving LPs considering all the possible solutions restricted to small portions of the graph. We then use that branch‐and‐cut within a GRASP that performs moves by solving to optimality subproblems corresponding to partial solutions. The computational experiments were conducted on 450 benchmark instances from the literature. Numerical results show improved best known (UBs) for almost all instances that could not be solved to optimality. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012