Speaker

Yinyu Ye

Professor of Management Science and Engineering
and, by courtesy, Electrical Engineering

Affiliation: Department of Management Science and Engineering
Stanford University

Abstract

A natural optimization model that formulates many online resource allocation and revenue management problems is the online linear program (LP) where the constraint matrix is revealed column by column along with the objective function. We provide a near-optimal algorithm for this surprisingly general class of online problems under the assumption of random order of arrival and some mild conditions on the size of the LP right-hand-side input. Our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from revealed columns in the previous period are used to determine the sequential decisions in the current period. Our algorithm has a feature of learning by doing", and the prices are updated at a carefully chosen pace that is neither too fast nor too slow. In particular, our algorithm doesn't assume any distribution information on the input itself, thus is robust to data uncertainty and variations due to its dynamic learning capability. Applications of our algorithm include many online multi-resource allocation and multi-product revenue management problems such as online routing and packing, online combinatorial auctions, adwords matching, inventory control and yield management.

This is a joint work with Shipra Agrawal and Zizhuo Wang.

Bio

Yinyu Ye received the B.S. degree in System Engineering from the Huazhong University of Science and Technology, Wuhan, China, and the M.S. and Ph.D. degrees in Management Science & Engineering from Stanford University, Stanford. Currently, he is a full Professor of Management Science and Engineering and Institute of Computational and Mathematical Engineering and the Director of the MS&E Industrial Affiliates Program, Stanford University. His current research interests include Continuous and Discrete Optimization, Mathematical Programming, Algorithm Design and Analysis, Computational Game/Market Equilibrium, Metric Distance Geometry, Graph Realization, Dynamic Resource Allocation, and Stochastic and Robust Decision Making, etc.

The following is a list of some of his main achievements:

• Recipient of the John von Neumann Theory Prize of 2009
• Recipient of the 2009 IBM Faculty Award.
• Elected Vice Chair of the SIAM Activity Group on Optimization (SIAG/OPT), 2008.
• The recipient of the 2007 Stanford Asian American Faculty of Year Award 
• The INFORMS (The Institute for Operations Research and The Management Science) Fellow since 2006 and the first recipient of the Farkas prize of the INFORMS Optimization
  Society in 2006.
• Selected as a highly cited mathematical researcher on http://www.ISIhighlycited.com 2004.
• The plenary and semi-plenary speakers of ISMP (International Symposium of Mathematical Programming) 2006 and 2000.
• Distinguished Speaker in High Performance Computation for Engineered Systems (HPCES), MIT, 2002.
• The Optimization Area Editor of Operations Research 2006-, the subject editor of Optimization and Engineering 2002- and the Co-Chief editor of Pacific J. of Optimization 2005-.