Collaborative Research: Performance Guarantees for Approximate Dynamic Programming Approaches to Pricing and Capacity Management

点击翻译按钮获取中文摘要

This project will benefit the U.S. economy and public quality of life by developing new solution methods for problems that involve dynamically managing the prices and limited resources to serve uncertain customer demands. Such pricing and capacity management problems occur in many settings, including selling processing capacity in cloud computing, pricing itineraries in airlines and hotels, and matching drivers with passengers in on-demand transportation. In these problems, finding the optimal course of action at any point in time requires keeping track of a large amount of information, including remaining processing times on thousands of servers, capacities left on hundreds of flights, and locations of thousands of drivers, along with forecasts of future needs. Existing solution methods often ignore the uncertainty in demand or the detailed customer arrival process. The fundamental research of this project will provide new knowledge and techniques for solving these challenging problems. The techniques will apply to a wide range of applications, will scale to large-scale problems brought by the information age, and will help make decisions at a rapid rate. This project will also broaden the participation of underrepresented groups and positively impact engineering education through the development of online certificate programs, shared data-sets, and industry collaborations. Dynamic programming is a general framework that can address dynamic decision-making problems under uncertainty, but dynamic programming formulations often end up with high-dimensional state variables, which make them difficult to solve. This research will develop approximate dynamic programming methods for a variety of pricing and capacity management problems that frequently occur in practice, including (a) pricing problems with reusable products, applicable to cloud computing systems where processing capacity is reusable, (b) pricing problems over a network of resources, applicable to airlines and hotels where there is an underlying network of resources and the sale of a product consumes a combination of resources, and (c) product pairing problems for upselling, applicable to online retail where additional product recommendations are made during checkout. The approximate dynamic programming methods will have performance guarantees. Some of these performance guarantees, especially those for pricing over a network of resources, will be the first of its kind. The methods will be flexible for a wide range of applications and will be scalable to industrial problem instances.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.