Practical Algorithms for Managing Uncertain Demand in Complex Systems

Abstract

This dissertation considers complex operational settings with uncertain demand. We consider three classes of problems, and show that for each one, a well designed policy can give close to optimal performance for either cost or profit metrics. To prove our results we use a variety of techniques from the theory of optimization and applied probability.First, we study assemble-to-order (ATO) problems, where a set of products are assembled from a set of common components. ATO problems with general structure and integrality constraints are well known to be difficult to solve, and we provide new insight into these issues by establishing worst-case approximation guarantees through various primal-dual analyses and LP rounding. First, we relax the one-period ATO problem using a natural newsvendor decomposition and use the dual solution for the relaxation to derive a lower bound on optimal cost, providing a tight approximation guarantee that grows with the maximum product size in the system. Then, we present LP rounding algorithms that achieve both asymptotic optimality as demand grows large, and a 1.8 approximation factor for any problem instance. Finally, we demonstrate that our one-period LP rounding results can be extended to analyze dynamic ATO problems. Specifically, we use our rounding scheme to develop an asymptotically optimal integral policy for dynamic ATO problems with backlogging and identical component lead-times.In the second class of problems, we consider a two-sided market with heterogeneous and stochastic values of matches between different units of supply and demand (such as those embedded in a network). With limited resources, a service provider can only choose a subset of locations in the market where matches can be made, and wants to choose a subset maximizing the expected value of matches. This problem captures decisions in a wide range of application domains, including those faced by franchise service providers, transportation-service platforms, and online advertisers. We demonstrate that the problem is NP-hard to approximate with a factor better than 1.58, and that the objective function does not enjoy the classic submodularity property, which would allow the application of known approximation guarantees for submodular function maximization. To overcome these hurdles, we propose a generalization of submodularity, called cover modularity, which allows us to prove approximation guarantees of 3 and 2.31 for an exchange algorithm and greedy algorithm, respectively. In order to establish these results, we prove general approximation guarantees for cover modular functions.For the final problem, we apply the classical operations management strategy of flexibility design to the context of online retailing fulfillment. More specifically, our method helps online retailers to make the strategic selection of a flexible fulfillment network and to improve their tactical decisions on which distribution center to use to fulfill online orders. To derive our results and insights, we use LP-based asymptotic analysis, stochastic programming, concepts from revenue management, and numerical simulations. We collaborate with a large online retailer to propose a data-driven online resource allocation model which captures the key features of the retailer's fulfillment network. We identify settings where the naive greedy policy performs poorly, and propose a spillover limit policy that is asymptotically optimal under a general setting. Finally, we use the spillover limit policy and a stochastic programming allocation policy to evaluate the benefit of a proposed flexible fulfillment network using data from our industrial collaborator. We estimate that our proposed flexible fulfillment network decreases the lost sales plus fulfillment costs by one percent, which equates to a profit improvement on the order of tens of millions of U.S. dollars.