On exact solutions for the minmax regret spanning tree problem
share
The Minmax Regret Spanning Tree problem is studied in this paper. This is a generalization of the well-known Minimum Spanning Tree problem, which considers uncertainty in the cost function. Particularly,it is assumed that the cost parameter associated with each edge is an interval whose lower and upperlimits are known, and the Minmax Regret is the optimization criterion. The Minmax Regret SpanningTree problem is an NP-Hard optimization problem for which exact and heuristic approaches have beenproposed. Several exact algorithms are proposed and computationally compared with the most effectiveapproaches of the literature. It is shown that a proposed branch-and-cut approach outperforms theprevious approaches when considering several classes of instances from the literature.
READ FULL TEXT