A branch and bound algorithm for the robust spanning tree problem with interval data

• Published in: European journal of operational research 2005-03, Vol.161 (3), p.771-779
• Main Authors: Montemanni, R., Gambardella, L.M.
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Branch & bound algorithms; Branch and bound; Exact sciences and technology; Flows in networks. Combinatorial problems; Interval data; Operational research and scientific management; Operational research. Management science; Operations research; Optimization; Robust optimization; Spanning tree problem; Studies
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2003.10.008

The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value. Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization. In this paper a branch and bound algorithm for the robust spanning tree problem is proposed. The method embeds the extension of some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted. Computational results obtained by the algorithm are presented. The technique we propose is up to 210 faster than methods recently appeared in the literature.