Perturbation algorithm for a minimax regret minimum spanning tree problem

• Authors: Mariusz MAKUCHOWSKI
• Languages of publication: EN

Abstracts

EN

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

EN

discrete optimization; robust optimization; perturbation algorithms; minimax regret

• Publisher: Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
• Journal: Operations Research and Decisions
• Year: 2014
• Volume: 24
• Issue: 1
• Pages: 37-49

Contributors

author

Mariusz MAKUCHOWSKI

• Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

References

• 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 algorith
• 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>.

Identifiers

DOI

10.5277/ord140103