Issue: 2014/Vol.24/No.1, Pages 37-49
PERTURBATION ALGORITHM FOR A MINIMAX REGRET MINIMUM SPANNING TREE PROBLEM
Mariusz Makuchowski
Cite as: M. Makuchowski. Perturbation algorithm for a minimax regret minimum spanning tree problem. Operations Research and Decisions 2014: 24(1), 37-49. DOI 10.5277/ord140103
Abstract
The problem of finding a robust spanning tree has been analysed. The problem consists of determining a minimum spanning tree of a graph with uncertain edge costs. We should determine a spanning tree that minimizes the difference in costs between the tree selected and the optimal tree. While doing this, all possible realizations of the edge costs should be taken into account. This issue belongs to the class of NP-hard problems. In this paper, an algorithm based on the cost perturbation method and adapted to the analysed problem has been proposed. The paper also contains the results of numerical experiments testing the effectiveness of the proposed algorithm and compares it with algorithms known in the literature. The research is based on a large number of various test examples taken from the literature.
Keywords: discrete optimization, robust optimization, perturbation algorithms, minimax regret
Received: 4 May 2013 Accepted: 23 January 2014