Theses Doctoral

Optimization and revenue management in complex networks

Yang, Shuoguang

This thesis consists of three papers in optimization and revenue management over complex networks: Robust Linear Control in Transmission Systems, Online Learning and Optimization Under a New Linear-Threshold Model with Negative Influence, and Revenue Management with Complementarity Products. This thesis contributes to analytical methods for optimization problems in complex networks, namely, power network, social network and product network.

In Chapter 2, we describe a robust multiperiod transmission planning model including renewables and batteries, where battery output is used to partly offset renewable output deviations from forecast. A central element is a nonconvex battery operation model plus a robust model of forecast errors and a linear control scheme. Even though the problem is nonconvex we provide an efficient and theoretically valid algorithm that effectively solves cases on large transmission systems.

In Chapter 3, we propose a new class of Linear Threshold Model-based information-diffusion model that incorporates the formation and spread of negative attitude. We call such models negativity-aware. We show that in these models, the expected positive influence is a monotone sub-modular function of the seed set. Thus we can use a greedy algorithm to construct a solution with constant approximation guarantee when the objective is to select a seed set of fixed size to maximize positive influence. Our models are flexible enough to account for both the features of local users and the features of the information being propagated in the diffusion. We analyze an online-learning setting for a multi-round influence-maximization problem, where an agent is actively learning the diffusion parameters over time while trying to maximize total cumulative positive influence. We develop a class of online learning algorithms and provide the theoretical upper bound on the regret.

In Chapter 4, we propose a tractable information-diffusion-based framework to capture complementary relationships among products. Using this framework, we investigate how various revenue-management decisions can be optimized. In particular, we prove that several fundamental problems involving complementary products, such as promotional pricing, product recommendation, and category planning, can be formulated as sub-modular maximization problems, and can be solved by tractable greedy algorithms with guarantees on the quality of the solutions. We validate our model using a dataset that contains product reviews and metadata from Amazon from May 1996 to July 2014.

We also analyze an online-learning setting for revenue-maximization with complementary products. In this setting, we assume that the retailer has access only to sales observations. That is, she can only observe whether a product is purchased from her. This assumption leads to diffusion models with novel node-level feedback, in contrast to classical models that have edge-level feedback. We conduct confidence region analysis on the maximum likelihood estimator for our models, develop online-learning algorithms, and analyze their performance in both theoretical and practical perspectives.


  • thumnail for Yang_columbia_0054D_16122.pdf Yang_columbia_0054D_16122.pdf application/pdf 1.54 MB Download File

More About This Work

Academic Units
Industrial Engineering and Operations Research
Thesis Advisors
Truong, Van-Anh
Bienstock, Daniel
Ph.D., Columbia University
Published Here
August 4, 2020