Approximation algorithms for a class of stochastic selection problems with reward and cost considerations
H. Edwin Romeijn, Professor and Chair, H. Milton Steward School of Industrial and Systems Engineering, Georgia Tech
Zohar M.A. Strinka, Department of Industrial and Operations Engineering, University of Michigan
Friday, March 25, 2016
Brickyard Engineering (BYENG) 210, Tempe campus [map]
Free to attend
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 more traditional risk-neutral expected-value objective as a special case. We use a combination of rounding and sample average approximation 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 test problems. We find that for our supply chain example, high-quality solutions can be found with small computational effort.
Edwin Romeijn received his Ph.D. in 1992 from Erasmus University Rotterdam in The Netherlands. He has been a faculty member at the Rotterdam School of Management, the University of Florida, and the University of Michigan. From 2012-2014 he was on leave from the latter institution to be a program director at the National Science Foundation for the main funding programs in the areas of fundamental and application-driven operations research and industrial engineering. Since January 2015 he is serving as the H. Milton and Carolyn J. Stewart School Chair of the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech. He has taught courses in operations research, stochastic processes, applied probability and statistics, supply chain management, and decision support systems. His research focuses on optimization theory and applications, in particular in the areas of health care and supply chains. He is the author of over one hundred peer reviewed journal publications.