Discrete optimization problems with random elements

Abstract

We consider stochastic discrete optimization problems (SDOPs) (eg. Knapsack, Travelling salesman problem etc) i.e. problems where some of the elements\' (e.g. cost of a path) could be random. We will consider problems in which the feasibility of a solution does not depend on the particular values the random elements in the problem take. Given a regret function, defined in this work, we introduce the concept of the risk associated with a solution, and define an optimal solution as one having the least possible risk.

We show that for SDOPs with one random element and with min-sum objective functions a least risk solution for the stochastic problem can be obtained by solving a non-stochastic counterpart where the latter is constructed by replacing the random element of the former with a suitable parameter. We show that the above surrogate is the mean if the stochastic problem has only one symmetrically distributed random element. We obtain bounds for this parameter for certain classes of asymmetric distributions and study the limiting behavior of this parameter in details under two asymptotic frameworks.

For similar SDOPs having multiple random elements, while the optimal solution, for a linear regret function, can be obtained by solving an auxiliary (non-stochastic) discrete optimization problem (DOP), the situation becomes complex under general regret function. We characterize a finite number of solutions which will include the optimal solution. We establish that the results from single dimension can be extended only partially for SDOPs with additional characteristics. We present a result where in selected cases, a complex SDOP may be decomposed into simpler ones facilitating the job of finding an optimal solution to the complex problem. We also propose numerical local search algorithms for obtaining an optimal solution.