Minimax regret spanning arborescences under uncertain costs

Conde, E; Candia, A.

Abstract

The paper considers a classical optimization problem on a network whose arc costs are partially known. It is assumed that an interval estimate is given for each arc cost and no further information about the statistical distribution of the truth value of the arc cost is known. In this context, given a spanning arborescence in the network, its cost can take on different values according to the choice of each individual arc cost, that is, according to the different cost scenarios. We analyze the problem of finding which spanning arborescence better approaches the optimal one under each possible scenario. The minimax regret criterion is proposed in order to obtain such a robust solution to the problem. In the paper, it is shown that a greedy-type algorithm can compute an optimal solution of this problem on acyclic networks. For general networks, the problem becomes NP-hard. In this case, the special structure of the optimization problem allows us to design a bounding process for the optimum value that will result in a heuristic algorithm described at the end of the paper. © 2006 Elsevier B.V. All rights reserved.

Más información

Título según WOS: Minimax regret spanning arborescences under uncertain costs
Título según SCOPUS: Minimax regret spanning arborescences under uncertain costs
Título de la Revista: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volumen: 182
Número: 2
Editorial: Elsevier
Fecha de publicación: 2007
Página de inicio: 561
Página final: 577
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0377221706008484
DOI:

10.1016/j.ejor.2006.07.036

Notas: ISI, SCOPUS