| Abstract |
This is a study of the behaviour of optimal solutions to combinatorial optimization problems (with either min-sum or min-max objective functions) when the costs of some of the elements in the ground sets of these problems vary. Denote the set of random elements by R. Since the optimal solution will depend on the costs realized by the random elements, which is not known beforehand, each solution S containing elements of R has an associated risk, measured by a risk function of the difference between the objective function value of S and that of the optimal solution at the costs that the elements of R realize. It is assumed that the probability distribution of the elements in R is known and is independent of each other. The study will look at decision rules that allow decision makers to choose solutions with minimum associated risk in such situations.
It can be shown that if the risk function is linear, the least risk solution will be the solution of the combinatorial optimization problem in which the costs of the elements of R are replaced by their expected values.
In this study, the assumption of linearity of risk functions will be released and changes in decision rules due to this relaxation will be examined. This kind of relaxation has practical significance, for example, in portfolio optimization; risk is usually measured in terms of variance, which is a quadratic function.
|