Policies for Two-Stage Stochastic Resource Allocation Problems

Abstract: Motivated by the general problem of allocating resources to users, we develop a two-stage stochastic optimization model and analyze its theoretical properties. The first-stage decision variables define two distinct classes of policies: immediate release policies and sequential release policies. In general, sequential release policies outperform immediate release policies. However, we identify conditions under which immediate release policies remain provably optimal. We further show that adopting one policy when the other is optimal can lead to arbitrarily poor outcomes. Although the second-stage decisions are fully determined by the first-stage variables, we prove that the resulting problem is weakly NP-complete. Finally, we present computational experiments that empirically illustrate the impact of following suboptimal policies. All presented materials are published and/or in the public domain.

Bio: Bismark Singh is an associate professor in operational research in the School of Mathematical Sciences at the University of Southampton, UK. He received a habilitation (2023) in mathematics from the Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany; PhD and MSc degrees in operations research from The University of Texas (UT) at Austin, US; and, a B.Tech. (2011) degree in chemical engineering from the Indian Institute of Technology (IIT) Delhi. Between 2016 and 2019 he held positions at Sandia National Laboratories, US in the Discrete Math & Optimization group. His research has been funded by agencies including the Deutsche Forschungsgemeinschaft (DFG), the Horizon 2020 program, the Bavarian State Ministry for Science and Art, and the US Department of Energy. He is a Senior Member of IEEE, a Fellow of Institute of Mathematics and its Applications, and an Associate Fellow of The OR Society. He is the Winner of the 2023 Mathematics Young Investigator Award. In 2024-25, he was a Distinguished Research Fellow at TU Dresden, Germany. For further information, visit: https://bissi1.github.io/.