Perturbation Algorithm for a Minimax Regret Minimum Spanning Tree Problem

Makuchowski, Mariusz

doi:10.5277/ord140103

Autor

Makuchowski Mariusz (Wrocław University of Technology)

Tytuł

Perturbation Algorithm for a Minimax Regret Minimum Spanning Tree Problem

Źródło

Operations Research and Decisions, 2014, vol. 24, no. 1, s. 37-49, rys., tab., bibliogr. 16 poz.

Słowa kluczowe

Badania operacyjne, Algorytmy, Przegląd literatury
Operations research, Algorithms, Literature review

Uwagi

summ.
This work was supported by the Polish Committee for Scientific Research, grant N N206 492938

Abstrakt

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. (original abstract)

Dostępne w

Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka SGH im. Profesora Andrzeja Grodka
Biblioteka Główna Uniwersytetu Ekonomicznego w Katowicach
Biblioteka Główna Uniwersytetu Ekonomicznego w Poznaniu
Biblioteka Główna Uniwersytetu Ekonomicznego we Wrocławiu

Pełny tekst

Bibliografia

ARON I., VAN HENTENRYCK P., A constraint satisfaction approach to the robust spanning tree with interval data, Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, Edmondton, Canada, 2002.
ARON I., VAN HENTENRYCK P., On the complexity of the robust spanning tree problem with interval data, Operations Research Letters, 2003, 32, 36-40.
BEZRUKOV S., KADERALI F., POGUNTKE W., On central spanning trees of a graph, Lecture Notes Computer Science, 1996, 1120, 53-58.
CONDE E., CANADIA A., Minimax regret spanning arborescences under uncertain costs, European Journal of Operational Research, 2007, 182 (2), 561-577.
KASPERSKI A., Discrete optimization with interval data: Minimax regret and fuzzy approach, Studies in Fuzziness and Soft Computing, Springer-Verlag, Berlin 2008, 228.
KASPERSKI A., KOBYLAŃSKI P., KULEJ M., ZIELIŃSKI P., Minimizing maximal regret in discrete optimization problems with interval data, [in:] Issues in Soft Computing Decisions and Operations Research, O. Hryniewicz, J. Kacprzyk, D. Kuchta (Eds.), Akademicka Oficyna Wydawnicza EXIT, Warsaw 2005, 193-208.
KASPERSKI A., MAKUCHOWSKI M., ZIELIŃSKI P., A tabu search algorithm for the minimax regret minimum spanning tree problem with interval data, Journal of Heuristics, 2012, 18 (4), 593-625.
KASPERSKI A., ZIELIŃSKI P., An approximation algorithm for interval data minmax regret combinatorial optimization problems, Information Processing Letters, 2006, 97 (5), 177-180.
KOUVELIS P., YU G., Robust discrete optimization and its applications, Kluwer Academic Publishers, 1997.
KRUSKAL J.B., On the shortest spanning subtree of graph and the traveling salesman problem, Proc. Amer. Math. Soc., 1956, 7, 48-50.
MONTEMANNI R., GAMBARDELLA L.M., A branch and bound algorithm for robust spanning tree problem with interval data, Operations Research Letters, 2005, 161, 771-779.
NIKULIN Y., Simulated annealing algorithm for the robust spanning tree problem, Journal of Heuristics, 2007, 14, 391-402.
PRIM R.C., Shortest connection networks and some generalizations, Bell System Technical Journal, 1957, 36, 1389-1401.
RIBEIRO C., UCHOA E., WERNECK R., A hybrid GRASP with perturbations for the Steiner problem in graphs, Technical Report, Computer Science Department, Catholic University of Rio de Janeiro, 2002.
YAMAN H., KARASAN O.E., PINAR M.C., The robust spanning tree with interval data, Operations Research Letters, 2001, 29, 31-40.
IBM ILOG, CPLEX Optimizer, http://www.ibm.com/software/commerce/optimization//cplexoptimizer.

Cytowane przez

ISSN

2081-8858

Język

eng

URI / DOI

BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

Meny główne