Warehouse Assortment Selection with Constant-Factor Guarantees via Birkhoff–von Neumann Decomposition

Xiaobo Li is an associate professor in the Department of Industrial Systems Engineering and Management at the National University of Singapore. He received his Ph.D. in Industrial Engineering from the University of Minnesota in 2018. His research focuses on robust optimization, discrete choice modeling, and dynamic programming, with applications spanning revenue management, data-driven decision-making, supply chain management, and humanitarian and sustainable operations.

The rapid growth of e-commerce has intensified the challenge of efficient order fulfillment, particularly as front-end warehouses operate under strict capacity constraints. In such systems, determining which products to stock at each warehouse is a critical driver of fulfillment cost, especially when customer orders ideally should be satisfied entirely from a single front-end warehouse. This paper develops a scalable heuristic for warehouse assortment selection in both single- and multi-warehouse settings, based on the Birkhoff--von Neumann (BvN) decomposition. The method begins by solving a linear programming relaxation of the original problem and uses its solution to form a doubly stochastic matrix. A BvN decomposition of this matrix then produces a set of feasible solutions, and the heuristic outputs the best-performing one. We show that this heuristic achieves constant-factor performance guarantees. The approximation ratio is bounded by the maximum order size in single–warehouse systems and by the ratio of the maximum order size to the positive fulfillment cost gap between the cheapest and second-cheapest warehouses in multi-warehouse systems. Remarkably, these guarantees hold under arbitrary demand distributions, providing the first distribution-free result for this setting. We further develop a reduced BvN algorithm that efficiently performs the decomposition in polynomial time and can incorporate business constraints such as non-overlapping assortments and full-coverage requirements. Extensive numerical experiments, including a real-world case study and synthetic instances, demonstrate that the proposed heuristic consistently outperforms existing algorithms, with performance gains that become more substantial as the number of products, warehouses, and order complexity increase.