Title: Managing E-commerce Fulfillment Networks: Subset Selection and Approximate Submodularity
Abstract: Many challenging problems in managing e-commerce fulfillment networks can be posed as subset selection problems: which fulfillment arcs to select during the network design phase, where to place each item (SKU) in the network during the inventory planning phase, and which distribution centers to use for each order in the fulfillment phase. These impactful problems are computationally challenging due to their combinatorial structure, and both the academic and practitioner communities have recognized the need to develop effective heuristics. The academic literature has long understood submodularity to be an invaluable structural property for analyzing subset selection problems, for the intuitive reason that local changes in the objective can be used to bound global changes. Unfortunately, most subset selection problems arising in the e-commerce setting lack submodularity, due to the inherent ``two-sided" nature of the supply and demand networks under consideration. We overcome this technical challenge using a novel form of approximate submodularity to analyze local search heuristics for these problems, proposing a general framework that provides new constant factor approximation guarantees for a broad class of objectives and constraint types. Further, from a practical perspective, our primal-dual proof technique reveals efficient surrogate functions that can be used to significantly reduce the computational burden of running local search heuristics: at each iteration our surrogatesrequire solving only one linear program (LP) to find an improving search direction, whereas naive methods require LP solves for every possible direction. Thus, for problems with large dimension, our algorithm can run several orders of magnitude faster than naive local search methods, making it well suited for implementation at scale.
Paper: The talk is based on these two papers: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3844987 and https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4810516
Bio: Levi DeValve is an Associate Professor of Operations Management at the University of Chicago Booth School of Business. He works on network inventory management problems including replenishment, fulfillment, and network design. His work has been recognized with awards in the INFORMS JFIG paper competition, the M&SOM practice-based research competition, and the IBM Service Science best student paper award.
