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 upper limits are known, and the Minmax Regret is the optimization criterion. The Minmax Regret Spanning Tree problem is an NP-Hard optimization problem for which exact and heuristic approaches have been proposed. Several exact algorithms are proposed and computationally compared with the most effective approaches of the literature. It is shown that a proposed branch-and-cut approach outperforms the previous approaches when considering several classes of instances from the literature.
On exact solutions for the Minmax Regret Spanning Tree problem / Francisco Pérez-Galarce;Eduardo Álvarez-Miranda;Alfredo Candia-Véjar;Paolo Toth. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 47:(2014), pp. 114-122. [10.1016/j.cor.2014.02.007]
On exact solutions for the Minmax Regret Spanning Tree problem
TOTH, PAOLO
2014
Abstract
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 upper limits are known, and the Minmax Regret is the optimization criterion. The Minmax Regret Spanning Tree problem is an NP-Hard optimization problem for which exact and heuristic approaches have been proposed. Several exact algorithms are proposed and computationally compared with the most effective approaches of the literature. It is shown that a proposed branch-and-cut approach outperforms the previous approaches when considering several classes of instances from the literature.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.