×

Reduction approaches for robust shortest path problems. (English) Zbl 1210.90137

Summary: We investigate the uncertain versions of two classical combinatorial optimization problems, namely the Single-Pair Shortest Path Problem (SP-SPP) and the Single-Source Shortest Path Problem (SS-SPP). The former consists of finding a path of minimum length connecting two specific nodes in a finite directed graph \(G\); the latter consists of finding the shortest paths from a fixed node to the remaining nodes of \(G\). When considering the uncertain versions of both problems we assume that cycles may occur in \(G\) and that arc lengths are (possibly degenerating) nonnegative intervals. We provide sufficient conditions for a node and an arc to be always or never in an optimal solution of the Minimax regret Single-Pair Shortest Path Problem (MSP-SPP). Similarly, we provide sufficient conditions for an arc to be always or never in an optimal solution of the Minimax regret Single-Source Shortest Path Problem (MSS-SPP). We exploit such results to develop pegging tests useful to reduce the overall running time necessary to exactly solve both problems.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows (1993), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ · Zbl 1201.90001
[2] Montemanni, R.; Gambardella, L. M., The robust shortest path problem with interval data via Benders’ decomposition, 4OR, 3, 315-328 (2005) · Zbl 1134.90538
[3] Kouvelis, P.; Yu, G., Robust discrete optimization and its applications (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA · Zbl 0873.90071
[4] Averbakh, I.; Lebedev, V., Interval data minmax regret network optimization problems, Discrete Applied Mathematics, 138, 3, 289-301 (2004) · Zbl 1056.90010
[5] Zielinski, P., The computational complexity of the relative robust shortest path problem with interval data, European Journal of Operations Research, 158, 570-576 (2004) · Zbl 1056.90125
[6] Kasperski, A.; Zielinski, P., The robust shortest path problem in series-parallel miltidigraphs with interval data, Operations Research Letters, 34, 69-76 (2006) · Zbl 1080.90058
[7] Karasan OE, Pinar MC, Yaman H. The robust shortest path problem with interval data. Technical Report, Bilkent University. Ankara, Turkey, http://www.optimization-online.org; Karasan OE, Pinar MC, Yaman H. The robust shortest path problem with interval data. Technical Report, Bilkent University. Ankara, Turkey, http://www.optimization-online.org
[8] Montemanni, R.; Gambardella, L. M.; Donati, A. V., A branch-and-bound algorithm for the robust shortest path problem with interval data, Operations Research Letters, 32, 225-232 (2004) · Zbl 1045.90086
[9] Montemanni, R.; Gambardella, L. M., An exact algorithm for the robust shortest path problem with interval data, Computers and Operations Research, 31, 1667-1680 (2004) · Zbl 1073.90055
[10] Yokoya, D.; Duin, C. W.; Yamada, T., A reduction approach to the repeated assignment problem, European Journal of Operations Research, 210, 2, 185-193 (2011) · Zbl 1210.90114
[11] Salazar-Neumann M. Advances in robust combinatorial optimization and linear programming. PhD thesis, G.O.M., Université Libre de Bruxelles (U.L.B.), Brussels, Belgium; 2010.; Salazar-Neumann M. Advances in robust combinatorial optimization and linear programming. PhD thesis, G.O.M., Université Libre de Bruxelles (U.L.B.), Brussels, Belgium; 2010.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.