Prof. Zhou Yuan
Tsinghua University
Talk: Online Linear Programming with Replenishment
Abstract: We study an online linear programming (OLP) model in which inventory is not provided upfront but instead arrives gradually through an exogenous stochastic replenishment process. This replenishment-based formulation captures operational settings, such as e-commerce fulfillment, perishable supply chains, and renewable-powered systems, where resources are accumulated gradually and initial inventories are small or zero. The introduction of dispersed, uncertain replenishment fundamentally alters the structure of classical OLPs, creating persistent stockout risk and eliminating advance knowledge of the total budget. We develop new algorithms and regret analyses for three major distributional regimes studied in the OLP literature: bounded distributions, finite-support distributions, and continuous-support distributions with a non-degeneracy condition. For bounded distributions, we design an algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret. For finite-support distributions with a non-degenerate induced LP, we obtain $\mathcal{O}(\log T)$ regret, and we establish an $\Omega(\sqrt{T})$ lower bound for degenerate instances, demonstrating a sharp separation from the classical setting where $\mathcal{O}(1)$ regret is achievable. For continuous-support, non-degenerate distributions, we develop a two-stage accumulate-then-convert algorithm that achieves $\mathcal{O}(\log^2 T)$ regret, comparable to the $\mathcal{O}(\log T)$ regret in classical OLPs. Together, these results provide a near-complete characterization of the optimal regret achievable in OLP with replenishment. Finally, we empirically evaluate our algorithms and demonstrate their advantages over natural adaptations of classical OLP methods in the replenishment setting.
Biography: Yuan Zhou is an Associate Professor at the Yau Mathematical Sciences Center, Tsinghua University. He received his B.Eng. in Computer Science from Tsinghua University in 2009 and his Ph.D. in Computer Science from Carnegie Mellon University in 2014. Prior to joining Tsinghua, he was an Applied Mathematics Instructor at MIT and an Assistant Professor at the University of Illinois Urbana–Champaign and Indiana University Bloomington. His research focuses on data-driven decision-making and artificial intelligence for science, with interests spanning operations research, machine learning, and optimization. He has published in leading venues in operations research and management science, machine learning, and theoretical computer science, including Operations Research, Management Science, Mathematics of Operations Research, Production and Operations Management, SIAM Journal on Optimization, Nature Machine Intelligence, Journal of Machine Learning Research, ICML, NeurIPS, ICLR, COLT, STOC, FOCS, and SODA. He also serves as an Associate Editor for Operations Research and Operations Research Letters.
