Discrete optimization problems with random cost elements

In a general class of discrete optimization problems, some of the elements mayhave random costs associated with them. In such a situation, the notion of optimalityneeds to be suitably modified. In this work we define an optimal solutionto be a feasible solution with the minimum risk. We focus on the minsumobjective function, for which we prove that knowledge of the mean values ofthese random costs is enough to reduce the problem into one with fixed costs.We discuss the implications of using sample means when the true means ofthe costs of the random elements are not known, and explore the relation betweenour results and those from post-optimality analysis. We also show thatdiscrete optimization problems with min-max objective functions depend moreintricately on the distributions of the random costs.