Leveraging Structure of Uncertainty for Adaptive Policies in Multistage Decision-Making

Han, Eojin

doi:https://doi.org/10.21985/n2-db8h-d288

Work

Leveraging Structure of Uncertainty for Adaptive Policies in Multistage Decision-Making

Public

Download PDF

Download All Files (.zip)

Multistage optimization is a prominent modeling tool to solve a broad range of dynamic decision-making problems in the presence of uncertainty. However, computing optimal policies is intractable, since they are obtained by considering all possible realizations of uncertainties and subsequent future decisions over time. To overcome these challenges, we present how the structure of uncertainty can be leveraged in a tractable fashion for solving multistage optimization problems. We consider three types of structure, where the uncertainty is divided in time, spatially partitioned, or lifted into higher-dimensional spaces. For each structure, we develop policies that are computationally attractive, while preserving the optimality or improving over the currently existing techniques. In Chapter 2, we develop a new class of periodic-affine policies that rely on the structure of uncertainty that is divided in time periods. Leveraging this subperiodic structure, the periodic-affine policies are obtained from a tractable algorithm, which iteratively solves smaller and computationally more attractive subproblems rather than a large-scale multistage optimization problem. Our framework is based on a general newsvendor network model, and hence, can be generalized to multi-dimensional settings with many features of uncertainties such as correlation. In this way, it offers a natural framework to study competing policies such as base-stock, affine, and approximative approaches with respect to their profit, sensitivity to parameters and assumptions, and computational scalability. We demonstrate advantages of the periodic-affine policies on the real-world sales data from one of India’s largest pharmacy retailers. In Chapter 3, we study spatial partitioning of uncertainty and propose policies that are interpretable and easy to implement, often preferred in real-world decision-making in many disciplines. These policies are achieved by partitioning the space of uncertainty realization and assigning a contingent decision to each piece, previously known as a concept of finite adaptability. We first show that the optimal partitioning can be characterized by “translated orthants,” which only require the problem structure and, hence, are free of modeling assumptions on the uncertainty. While we prove that finding the optimal partitioning with orthants is hard, we propose a specific orthant partitioning scheme that enables efficient computation. By leveraging the geometry of this partitioning, it allows us to establish a-priori performance bounds, which generalize the existing bounds in the literature. We also characterize worst-case probability distributions, and consequently, construct posterior lower bounds, offering an additional tool to assess suboptimality of our policies. We apply our partitioning to a stylized inventory routing problem with mixed-integer recourse and the case of a pharmacy retailer to demonstrate its performance. In Chapter 4, we consider the structured uncertainty in higher dimensions, which contains the original uncertainty space as its subspace. Such sets are called lifted uncertainty sets, and are defined to derive nonlinear policies. However, previously proposed approaches require pre-determined characterization of the nonlinear functional structure of policies, which can be ineffective and computationally inefficient. We propose two specific lifting techniques, namely the point-based and policy-based liftings, both exploiting the geometry of uncertainty sets to construct lifted sets. In this way, we obtain generalized nonlinear policies by efficiently identifying problem-specific nonlinear functions of uncertainties. Numerical experiments on two-stage problems and multi-period inventory control problems demonstrate that our policies outperform other well-established policies without losing computational tractability. Overall in this dissertation, our findings suggest that exploiting the structural properties of uncertainty can significantly improve dynamic policies in multistage optimization. Our frameworks are based on generic problems, and hence, allow multiple extensions to domain-specific context and inspire to explore other structures of uncertainty. To this end, this dissertation provides a new direction on developing structure-based policies in dynamic decision-making under uncertainty.

Creator