Perturbation algorithm for a minimax regret minimum spanning tree problem
Journal Title: Operations Research and Decisions - Year 2014, Vol 24, Issue 1
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.
Authors and Affiliations
Mariusz Makuchowski
Keywords
Related Articles
- EP ID EP168410
- DOI -
- Views 41
- Downloads 0
The optimal portfolio under VaR and ES
An analysis of the dependence structure among certain European indices (FTSE100, CAC40, DAX30, ATX20, PX, BUX and BIST) has been conducted. The main features of the financial data were studied: asymmetry, fat-tailedness...
Robust bi-level optimization for an opportunistic supply chain network design problem in an uncertain and risky environment
This paper introduces the problem of designing a single-product supply chain network in an agile manufacturing setting under a vendor managed inventory (VMI) strategy to seize a new market oppor-tunity. The problem addre...
Energy prosumers: profiling the energy microgeneration market in Lower Silesia, Poland
Microgeneration of energy has the potential to become an important component of the energy policy of many governments, because it may substantially lower carbon emissions and reduce the need for new infrastructure. Never...
Optimal ordering quantities for substitutable items under joint replenishment with cost of substitution
An inventory system of two mutually substitutable items has been studied where an item is out of stock, demand for it is met by the other item and any part of demand not met due to unavailability of the other item is los...
Using a multicriteria interactive approach in scheduling non-critical activities
A typical project consists of many activities. Logical dependencies cause some of them to be critical and some non-critical. While critical activities have a strict start time, in some projects the problem of selecting t...