Order-optimal correlated rounding for fulfilling multi-item e-commerce orders

Problem definition: We study the dynamic fulfillment problem in e-commerce, in which incoming (multi-item) customer orders must be immediately dispatched to (a combination of) fulfillment centers that have the required inventory. Methodology/results: A prevailing approach to this problem, pioneered by Jasin and Sinha in 2015, has been to write a “deterministic” linear program that dictates, for each item in an incoming multi-item order from a particular region, how frequently it should be dispatched to each fulfillment center (FC). However, dispatching items in a way that satisfies these frequency constraints, without splitting the order across too many FCs, is challenging. Jasin and Sinha in 2015 identified this as a correlated rounding problem and proposed an intricate rounding scheme that they proved was suboptimal by a factor of at most ≈q/4 on a q-item order. This paper provides, to our knowledge, the first substantially improved scheme for this correlated rounding problem, which is suboptimal by a factor of at most 1+ln(q). We provide another scheme for sparse networks, which is suboptimal by a factor of at most d if each item is stored in at most d FCs. We show both of these guarantees to be tight in terms of the dependence on q or d. Our schemes are simple and fast, based on an intuitive idea; items wait for FCs to “open” at random times but observe them on “dilated” time scales. This also implies a new randomized rounding method for the classical Set Cover problem, which could be of general interest. Managerial implications: We numerically test our new rounding schemes under the same realistic setups as Jasin and Sinha and find that they improve runtimes, shorten code, and robustly improve performance. Our code is made publicly available online.History: This paper was selected for Fast Track in the M&SOM Journal from the 2022 MSOM Supply Chain Management SIG Conference.Funding: This research was partially funded by a grant from Amazon.com Inc., which was awarded through collaboration with the Columbia Center of AI Technology (CAIT).