Minimax regret spanning arborescences under uncertain costs

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.07.036 Byline: Eduardo Conde (a), Alfredo Candia (b) Keywords: Robust optimization; Minimum spanning arborescences; Edmonds' algorithm 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. Author Affiliation: (a) Department of Statistic and Operations Research, Facultad de Matematicas, Universidad de Sevilla, Campus Universitario de Reina Mercedes, 41012 Sevilla, Spain (b) Department of Computer Science, Universidad de Talca, Merced 437, Curico, Chile Article History: Received 25 November 2005; Accepted 21 July 2006