Optimal Correlated Rounding for Multi-item Orders in E-commerce Fulfillment

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. The problem takes place over a finite time horizon, representing the duration until the next inventory replenishment. A prevailing approach to this problem, pioneered by Jasin and Sinha (2015), is to write a ``deterministic'' LP that dictates how frequently inventory from each FC (fulfillment center) should be used to fulfill each item, in different orders from different regions. This allows the fulfillment decision for each order to be made independently. However, making this decision for a single multi-item order is still challenging -- how can we avoid splitting the order across too many FC's, while satisfying the inventory frequency constraints? Jasin and Sinha identify this as a correlated rounding problem and propose an intricate rounding scheme, which is suboptimal by a factor of $\approx q/4$ on a $q$-item order. In this paper we provide to our knowledge the first substantially improved correlated rounding scheme, which is suboptimal by a factor of only $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$ FC's. We show both of these guarantees to be optimal in terms of the dependence on $q$ or $d$, by reducing to the classical Set Cover problem. Our schemes are also simple and fast, based on an intuitive new idea -- items wait for FC's to ``open'' at random times, but observe them on ``dilated'' time scales in order to satisfy the inventory frequency constraints. We numerically test our new rounding schemes under the same realistics setups as Jasin and Sinha and find that they improve runtimes, shorten code, and robustly improve performance. Our code is made publicly available.