On solving some stochastic discrete optimization problems under general regret function

Abstract

In this paper we consider stochastic discrete optimization problems (DOP) in which feasible solutions remain feasible irrespective of the randomness of the problem parameters. We introduce the concept of the risk associated with a solution and define optimal solution in terms of having least possible risk. We show that a least risk solution can be obtained by solving a non-stochastic discrete optimization  problem similar to the stochastic problem in certain problems and present results regarding the generation of the non-stochastic problem in terms of finding the parameter of the distribution which may act as surrogate for the random element in its no-stochastic counterpart. While this surrogate in the mean for a linear regret function, the situation is complex under general regret. Our results show that the above result continues to hold (in general) if the DOP has only one random element having symmetric distribution. We obtain some bounds for this parameter for certain group of asymmetric distributions and study its limiting behaviour under two asymptotic setup. We establish through various examples that the results from uni-dimensional case cannot be extended to stochastic DOP with multiple random element with any reasonable generality. However, we characterize a finite number of solutions which will include the optimal solution in this case. An heuristic based on local search type algorithm is also devised when the number of random elements is too high, and we study the performance of this algorithm through simulation.