Optimizing Inventory Placement for a Downstream Online Matching Problem

Problem definition: We study the inventory placement problem of splitting [Formula: see text] units of a single item across warehouses in advance of a downstream online matching problem that represents the dynamic fulfillment decisions of an e-commerce retailer. This is a challenging problem both theoretically, due to the computational complexity of the downstream matching problem, and practically, as the fulfillment team continuously updates its algorithm while the placement team lacks direct evaluation of placement decisions. Methodology/results: We compare the performance of three placement procedures based on optimizing surrogate functions that have been studied and applied: Offline, Myopic, and Fluid placement. On the theory side, we show that optimizing inventory placement for the Offline surrogate leads to an [Formula: see text]-approximation for the joint placement and fulfillment problem under any demand model that admits an [Formula: see text]-competitive fulfillment policy. We assume [Formula: see text] is an upper bound on how many warehouses can serve any demand location. The crux of our theoretical contribution is to use randomized rounding to derive a tight [Formula: see text]-approximation for the integer programming problem of optimizing the Offline surrogate. We further show how to extend this result to a multi-SKU setting, improving upon the best known approximation of [Formula: see text]. We use statistical learning to show that rounding after optimizing a sample-average Offline surrogate, which is necessary due to the exponentially-sized support, indeed has vanishing loss. On the experimental side, we evaluate how different combinations of placement and fulfillment procedures perform on a wide array of synthetic instances. When coupled with a good fulfillment procedure, optimizing the Offline surrogate performs best even compared to computationally-intensive simulation procedures, corroborating our theory. Managerial implications: Theoretical guarantees and extensive numerics both suggest that the placement team should optimize the (optimistic) Offline surrogate, assuming the fulfillment team has a good algorithm. Otherwise, the placement team could optimize the (pessimistic) Myopic surrogate instead.