Department of Industrial Engineering & Decision Analytics [Joint IEDA/ISOM] seminar - Sequential Policies and the Distribution of their total Rewards in Dynamic and Stochastic Knapsack Problems
Supporting the below United Nations Sustainable Development Goals:支持以下聯合國可持續發展目標：支持以下联合国可持续发展目标：
We study a dynamic and stochastic knapsack problem in which a decision maker is sequentially presented with n items with unitary rewards and independent weights that are drawn from a known continuous distribution. The decision maker seeks to maximize the expected reward she collects by including items in a knapsack while satisfying a capacity constraint, and while making terminal decisions as soon as each item weight is revealed. We propose a reoptimized heuristic and compare its total rewards with that of the optimal dynamic programming policy. We show that the two total rewards have the same asymptotic mean, the same asymptotic variance, and the same limiting distribution. In contrast, we also note that other asymptotically optimal heuristics that have been considered in the literature have different (larger) higher moments and different limiting distributions. (Joint work with Xinchang Xie and Yun-Tung Kuo.)
Prof. Alessandro Arlotto is an Associate Professor at the Fuqua School of Business, Duke University, and Department of Mathematics, Duke University. His research interests include Applied probability, stochastic modeling, stochastic dynamic programming, combinatorial optimization, applications to management sciences and economics, and election analytics. He earned his Ph.D. in in Managerial Science and Applied Economics, University of Pennsylvania, Philadelphia in 2012.