Montemanni, Roberto; Gambardella, Luca Maria The robust shortest path problem with interval data via Benders decomposition. (English) Zbl 1134.90538 4OR 3, No. 4, 315-328 (2005). Summary: Many real problems can be modelled as robust shortest path problems on digraphs with interval costs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs. In this paper we discuss the application of a Benders decomposition approach to this problem. Computational results confirm the efficiency of the new algorithm. It is able to clearly outperform state-of-the-art algorithms on many classes of networks. For the remaining classes we identify the most promising algorithm among the others, depending of the characteristics of the networks. Cited in 34 Documents MSC: 90C47 Minimax problems in mathematical programming 52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut Keywords:shortest path problem; robust optimization; interval data; Benders decomposition PDFBibTeX XMLCite \textit{R. Montemanni} and \textit{L. M. Gambardella}, 4OR 3, No. 4, 315--328 (2005; Zbl 1134.90538) Full Text: DOI