Dynamic preprocessing for the minmax regret robust shortest path problem with finite multi-scenariosby Marta M.B. Pascoal, Marisa Resende

Discrete Optimization


Theoretical Computer Science / Computational Theory and Mathematics / Applied Mathematics


A multi-objective shortest path problem

Kazuyoshi Wakuta

On the complexity of minmax regret linear programming

Igor Averbakh, Vasilij Lebedev

A note on the constrained shortest-path problem

Arun K. Pujari, Suneeta Agarwal, V. P. Gulati

A note on shortest path problems with forbidden paths

Olivia J. Smith, Martin W.P. Savelsbergh


Discrete Optimization ( ) –

Contents lists available at ScienceDirect

Discrete Optimization www.elsevier.com/locate/disopt

Dynamic preprocessing for the minmax regret robust shortest path problem with finite multi-scenarios

Marta M.B. Pascoal∗, Marisa Resende

Department of Mathematics, University of Coimbra, Apartado 3008, EC Santa Cruz, 3001-501 Coimbra, Portugal

Institute for Systems Engineering and Computers – Coimbra (INESCC), Rua Antero de Quental, 199, 3000-033 Coimbra, Portugal a r t i c l e i n f o

Article history:

Available online xxxx


Robust shortest path

Discrete scenarios

Dynamic preprocessing a b s t r a c t

The minmax regret robust shortest path problem aims at finding a path that minimizes the maximum deviation from the shortest paths over all scenarios. It is assumed that different arc costs are associated with different scenarios. This paper introduces a technique to reduce the network, before a minmax regret robust shortest path algorithm is applied. The preprocessing method enhances others explored in previous research. The introduced method acts dynamically and allows to update the conditions to be checked as new network nodes that can be discarded are identified. Computational results on random and Karasan networks are reported, which compare the dynamic preprocessing algorithm and its former static version.

Two robust shortest path algorithms as well as the resolution of a mixed integer linear formulation by a solver are tested with and without these preprocessing rules. © 2015 Elsevier B.V. All rights reserved. 1. Introduction

One approach for dealing with costs uncertainty is to consider several possible scenarios. In the case of the shortest path problem this is done either by associating a discrete set of costs with each arc, or by assuming each arc cost varies within an interval. In this paper, the former case is considered for the minimax regret robust shortest path problem, here simply called robust shortest path problem. This problem consists of finding a path between two nodes of a network, which minimizes the maximum regret cost of each path towards the shortest path, for all scenarios.

Yu and Yang [1] and, more recently, Pascoal and Resende [2], developed algorithms for the robust shortest path problem. Later, inspired by the works of Karasan, Pinar and Yaman [3] and then Catanzaro, Labbe´ and Salazar-Neumann [4], for the interval data case, Pascoal and Resende [5] presented theoretical results ∗ Corresponding author at: Department of Mathematics, University of Coimbra, Apartado 3008, EC Santa Cruz, 3001-501

Coimbra, Portugal. Tel.: +351 239 791150; fax: +351 239 832568.

E-mail addresses: marta@mat.uc.pt (M.M.B. Pascoal), mares@mat.uc.pt (M. Resende). http://dx.doi.org/10.1016/j.disopt.2015.11.001 1572-5286/© 2015 Elsevier B.V. All rights reserved. 2 M.M.B. Pascoal, M. Resende / Discrete Optimization ( ) – and algorithms that allow to reduce the network before a robust shortest path algorithm is applied. These preprocessing techniques can identify a priori arcs that are certainly part of any optimal solution, as well as nodes that do not belong to any optimal solution, in order to be deleted later.

The goal of this work is to enhance the preprocessing strategy developed in [5] for nodes. The improvement consists in developing a dynamic rule, in the sense that it is updated as the preprocessing algorithm runs and paths are computed. The idea behind this improvement is to further reduce the network before a robust shortest path algorithm is applied, that is, to increase the number of detected nodes that do not belong to any optimal solution. The latest aspect concerns limiting the number of scenarios to consider in the tests, and thus to save computational time. Empirical experiments compare the new rules with the former. Even though the extension of the rule introduced in [5] for detecting arcs in optimal solutions is expected to enhance the former, the performed tests did not show its usefulness in practice. For this reason that rule is omitted in the following. The interested reader may consult [6] for further details.

The remainder of the paper contains five other sections. Notation and concepts related with the robust shortest path problem are introduced in the next one. In addition, a brief sketch of the labeling and the hybrid robust shortest path algorithms presented in [2] is given. Section 3 is dedicated to the development of the new preprocessing rule and of the algorithm that implements it. An example is provided in Section 4.

Results of computational tests on random and Karasan instances, comparing the new rule and its original static version, when used together with the labeling and the hybrid approaches, as well as with using CPLEX for solving a mixed integer formulation of the robust shortest path problem, are reported and discussed in

Section 5. Conclusions are drawn in Section 6. 2. Preliminary concepts

A finite multi-scenario model is represented as G(V,A, Sk), where G is a directed graph with a set of nodes V = {1, . . . , n}, a set of m arcs A ⊆ {(i, j) : i, j ∈ V and i ̸= j} and a finite set of scenarios

Sk := {1, . . . , k}, k > 1. The density or average degree of G is denoted by d, which is given by d = m/n.

For each arc (i, j) ∈ A, csij represents its cost in scenario s, s ∈ Sk. It is assumed that the graph contains no parallel arcs.

A path from i to j, i, j ∈ V , in graph G, also called an (i, j)-path, is an alternating sequence of nodes and arcs of the form p = ⟨v1, (v1, v2), v2, . . . , (vr−1, vr), vr⟩, with v1 = i, vr = j and where vl ∈ V , for l = 2, . . . , r − 1, and (vl, vl+1) ∈ A, for l = 1, . . . , r − 1. Because it is assumed that graphs do not contain parallel arcs, in the following paths will be represented simply by their sequence of nodes.

The set of arcs (nodes) in a path p is denoted by A(p) (V (p)). Given two paths p, p′, such that the destination node of p is also the initial node of p′, the concatenation of p and p′ is the path formed by p followed by p′, and is denoted by p  p′. The cost of a path p in scenario s, s ∈ Sk, is defined by cs(p) =  (i,j)∈A(p) csij . (1)