Dual-sourcing inventory systems, in which one supplier is faster (i.e., express) and more costly, while the other is slower (i.e., regular) and cheaper, arise naturally in many real-world supply chains. These systems are notoriously difficult to optimize because of the complex structure of the optimal solution and the curse of dimensionality, having resisted solution for over 40 years. Recently, so-called tailored base-surge (TBS) policies have been proposed as a heuristic for the dual-sourcing problem. Under such a policy, a constant order is placed at the regular source in each period, while the order placed at the express source follows a simple order-up-to rule. Numerical experiments by several authors have suggested that such policies perform well as the lead time difference between the two sources grows large, which is exactly the setting in which the curse of dimensionality leads to the problem becoming intractable. However, providing a theoretical foundation for this phenomenon has remained a major open problem. In this paper, we provide such a theoretical foundation by proving that a simple TBS policy is indeed asymptotically optimal as the lead time of the regular source grows large, with the lead time of the express source held fixed. Our main proof technique combines novel convexity and lower-bounding arguments, an explicit implementation of the vanishing discount factor approach to analyzing infinite-horizon Markov decision processes, and ideas from the theory of random walks and queues, significantly extending the methodology and applicability of a novel framework for analyzing inventory models with large lead times recently introduced by Goldberg and coauthors in the context of lost-sales models with positive lead times. This paper was accepted by Gad Allon, operations management.

Given an input graph [Formula: see text], we consider the problem of designing a sparse subgraph [Formula: see text] with [Formula: see text] that supports a large matching after some nodes in V are randomly deleted. We study four families of sparse graph designs (namely, clusters, rings, chains, and Erdős–Rényi graphs) and show both theoretically and numerically that their performance is close to the optimal one achieved by a complete graph. Our interest in the stochastic sparse graph design problem is primarily motivated by a collaboration with a leading e-commerce retailer in the context of its middle-mile delivery operations. We test our theoretical results using real data from our industry partner and conclude that adding a little flexibility to the routing network can significantly reduce transportation costs. This paper was accepted by David Simchi-Levi, optimization. Funding: This work was supported by the University of Chicago Booth School of Business, an Alibaba Cainiao Research Grant, and the Singapore Ministry of Education [NUS Startup Grant WBS A-0003856-00-00]. Supplemental Material: Data and the online appendix are available at https://doi.org/10.1287/mnsc.2022.01588 .