Approximation Algorithms for a Class of Stochastic Selection Problems with Reward and Cost Considerations

We study a class of problems with both binary selection decisions and associated continuous choices that result in stochastic rewards and costs. The rewards are received based on the decision maker's selection, and the costs depend both on the decisions and realizations of the stochastic variables. We consider a family of risk-based objective functions that contains the traditional risk-neutral expected-value objective as a special case. A combination of rounding and sample average approximation is used to produce solutions that are guaranteed to be close to the optimal solution with high probability. We also provide an empirical comparison of the performance of the algorithms on a set of randomly generated instances of a supply chain example problem. The computational results illustrate the theoretical claims in the paper that, for this problem, high-quality solutions can be found with small computational effort. Funding: This research was conducted with government support under and awarded by a Department of Defense (DoD), Air Force Office of Scientific Research, National Defense Science and Engineering Graduate (NDSEG) Fellowship, 32 CFR 168a. Keywords: two-stage stochastic optimization * selection * resource allocation * approximation algorithms
1. Introduction In this paper we study a class of two-stage stochastic selection problems with recourse and develop approximation algorithms to efficiently solve them. In particular, a subset of options [...]