This Faculty Early Career Development (CAREER)research proposes to support the development of a modeling and algorithmic framework for solving large-scale real-time stochastic optimization problems. This research will focus on a setting where distributions of the underlying uncertainty are not known. The decision maker in this environment often faces a large number of alternatives and must make a decision in real-time based on high-volume data streams. By exploiting specific structures of each problem, this research will develop methodologies that combine real-time decision-making with approximation algorithms for solving complex stochastic optimization problems having large strategy sets. The research will investigate applications of these algorithms to problems in search-based advertising and supply chain management by working with industry partners. In addition, the outcome of the research will be integrated into an interactive teaching module or a case study.
The proposed research encompasses many problems in the current information-driven environment, including ad placement in search-based advertising services, inventory management for online retailers, and the multi-armed bandit problem. If successful, the research will result in a unifying framework for studying and analyzing this class of problems, along with a suite of algorithms applicable to these problems. The research will establish new techniques for extending the performance guarantee of approximation algorithms to reflect long-run average performance of the system, and provide new methodologies for improving the convergence rates by leveraging special structures within each problem. Extensive collaboration with companies in the industry and the integration of these relationships to enrich the classroom experience for students will be an important outcome of this project.
The objective of the award is to develop effective algorithms for high-dimensional complex stochastic optimization problems involving large structured decision sets and high-volume data streams, with applications to revenue management, dynamic pricing, and resource allocations. Intellectual Merits: During the lifetime of the award, we have developed many innovative algorithms and solution methods for the structured multiarmed bandit problems, dynamic assortment optimization, and the d-level nested logit model. We will briefly describe each problem and discuss our contributions in each area. Motivated by applications in online advertising, we consider the structured multiarmed bandit problem where the expected payoff of each decision is unknown a priori, and we only observe noisy samples of the reward. We assume that the mean reward of each decision is a linear function of the decision’s attributes. For example, if each decision corresponds to an advertisement to be shown to the user, the attributes of the ad might correspond to its content, popularity, or user ratings. Our goal is to develop an algorithm for choosing a sequence of decisions that maximizes the total expected reward. Since the mean reward of each decision is unknown, we need to simultaneously estimate the reward of the arms and choose the best decision based on the available information. In this ``learning and earning’’ environment, we develop a method that achieves the best possible reward, and they have been applied to problems in online advertising and dynamic assortment optimization. The results are published in IEEE Transaction on Automatic Control, Mathematics of Operations Research, and Operations Research. In the dynamic assortment optimization, we consider the problem of real-time optimization of personalized assortments. This problem is motivated by the availability of real-time data on customer characteristics, we consider the problem of personalizing the assortment of products to each arriving customer. Through actual sales data from an online retailer, we demonstrate that personalization based on each customer's location can lead to over 10% improvements in revenue, compared to a policy that treats all customers the same. We propose a family of simple and effective algorithms, called Inventory-Balancing, for real-time personalized assortment optimization, that do not require any forecasting: An Inventory-Balancing algorithm, maintains a "discounted-revenue index" for each product, in which the (actual) revenue is multiplied by a (virtual) discount factor that depends on the fraction of the product's remaining inventory. Upon an arrival of each customer, based on the customer's type, the algorithm offers to her the assortment that maximizes the expected discounted revenue. In addition to personalization, we have also considered the assortment packing problem in which a firm must decide, in advance, the release date of each product in a given collection over a selling season. This problem is motivated by retailers' frequent introduction of new items to refresh product lines and maintain their market share. Our formulation models the trade-offs among profit margins, preference weights, and limited life cycles. These works result in 2 papers that have been published in Management Science. Finally, we consider the assortment and price optimization problems under the d-level nested logit model. We provide a new formulation of the d-level nested logit model using a tree of depth d. Our formulation enables us to study two canonical revenue management problems under this model: finding the optimal assortment assuming fixed prices, and determining the revenue-maximizing prices for a portfolio of products. We establish structural properties and develop an efficient algorithm for computing the optimal assortment. For price optimization, although the expected revenue function is not concave, we develop an iterative algorithm that generates a sequence of prices converging to a stationary point. Numerical experiments show that our method converges much faster than gradient-based methods, by many orders of magnitude. To our knowledge, these results are the first of its kind for the d-level nested logit model. Broader Impacts: Building upon my experience with industries, the award has results in development of new courses that integrate industry collaboration to enrich the classroom experience for students. During the lifetime of the award, I have developed a new course called The Analytics Edge, which is targeted to undergraduate and master students. The course introduces students to the cutting-edge applications of optimization and data analytics. Some of these course materials are drawn from the research that I have conducted during the lifetime of this award. The responses from the students have been very positive.
