Louis Chen

Louis Chen

Assistant Professor

Talks and presentations

Distributionally Robust Influence Maximization

August 23, 2021

Talk, IFORS 2021, Online

We propose and study a distributionally robust influence maximization problem. Unlike the classic Independent Cascade model proposed in Kempe, Kleinberg, and Tardos (2003), we consider a model that involves an adversarial response to the selection of seed set. More precisely, rather than the spread of influence being determined by the independent coupling of random arcs, the spread of influence will be determined by an adversarial coupling of random arcs in response to any selection of seed set. Similarly to traditional stochastic models, the optimization problem remains NP-Hard. However, in contrast, with this newly introduced robust model, both the influence function and any node’s likelihood of being influenced can now be efficiently computed; furthermore, we show that even with an adversarial coupling, the greedy algorithm still guarantees a (1 - 1/e) - approximation of the optimum, as in the Independent Cascade model. Finally, we consider computational comparisons through experiments.

Correlation Robust Influence Maximization

December 06, 2020

Talk, NEURIPS 2020, Online

We propose and study a distributionally robust influence maximization problem. Unlike the classic Independent Cascade model proposed in Kempe, Kleinberg, and Tardos (2003), we consider a model that involves an adversarial response to the selection of seed set. More precisely, rather than the spread of influence being determined by the independent coupling of random arcs, the spread of influence will be determined by an adversarial coupling of random arcs in response to any selection of seed set. Similarly to traditional stochastic models, the optimization problem remains NP-Hard. However, in contrast, with this newly introduced robust model, both the influence function and any node’s likelihood of being influenced can now be efficiently computed; furthermore, we show that even with an adversarial coupling, the greedy algorithm still guarantees a (1 - 1/e) - approximation of the optimum, as in the Independent Cascade model. Finally, we consider computational comparisons through experiments.

Distributionally Robust Optimal Omnichannel Stocking Decisions in Quick Fulfilment Systems

July 01, 2019

Talk, Manufacturing and Service Operations Management Conference (2019), Singapore

This work is inspired by the daily operations of Hema supermarket, which is a recently established “new retail” model by Alibaba Group, China. In a Hema supermarket store, a single SKU may be presented with demand in the form of multiple channels. The challenge facing Hema is the question of how many units to stock in total between the warehouse and the store-front in advance of uncertain demand that arises in several consecutive time frames, each 30 minutes long. In this work, we provide the first distributionally robust optimization study in the setting of omnichannel inventory management, wherein we are to make a stocking decision robust to an adversary’s choice of coupling of available (marginal) demand distributions by channel and by time frame. The adversary’s coupling decision amounts to designing a random mathematical program with equilibrium constraints (MPEC). And we provide both a structural analysis of the adversary’s choice of couplingas well as an efficient procedure to find this coupling. In general, the overall distributionally robust stocking problem is non-concave. We provide sufficient conditions on the cost parameters under which this problem becomes concave, and hence tractable. Finally, we conduct experiments with Hema’s data. In these experiments, we compare and contrast the performance of our distributionally robust solution with the performance of a naive Newsvendor-like solution on various SKUs of varying sales volume and number of channels on a 5-hour time window from 2pm - 7pm on weekends. Numerical experiments show that the distributionally robust solutions generally outperform the stochastic Newsvendor-like solution. Furthermore, and interestingly, in all of our experiments, the distributionally robust inventory decision problems presented by the historical data provided by Hema are in fact concave.

Distributionally Robust Max Flow

November 06, 2018

Talk, INFORMS Annual Meeting (2018), Phoenix, Arizona

In this talk, we consider the problem of distributionally robust network design. In this problem, the decision maker is to decide on the prepositioning of resources on arcs in a given s-t flow network in anticipation of an adversary’s selection of a probability distribution for the arc capacities, aimed to minimize the expected max flow. The adversary’s selection is limited to those distributions that are couplings of given arc capacity distributions, one for each arc. We show that we can efficiently solve the distributionally robust network design problem in the case of finite-supported marginals. Further, we take advantage of the network setting to efficiently solve for the distribution the adversary responds with. The primal-dual formulation of our previous work takes on a striking form in this study. As one might expect, the form relates to the well-known Max Flow, Min-Cut theorem. And this leads to the intriguing interpretation as a 2-player, zero-sum game wherein player 1 chooses what to set the arc capacities to and player 2 chooses an s-t cut. Essential to our analysis is the finding that the problem of finding the worst-case coupling of the stochastic arc capacities amounts to finding a distribution over the set of s-t cuts- this distribution being among the mixed strategies that player 2 would play in a Nash equilibrium. Furthermore, the support of such a distribution is a nested collection of s-t cuts, which implies an efficiently sized solution.

Distributionally Robust Linear and Discrete Optimization with Marginals

July 05, 2018

Talk, 23rd International Symposium on Mathematical Programming, Bordeaux, France

We study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to be specified up to only the marginal distributions. We provide a primal-dual formulation for this problem. Though the robust bound is NP-hard, we identify a sufficient condition for polynomial time solvability using extended formulations. This generalizes the known tractability results under marginal information from 0-1 polytopes to a class of integral polytopes and has implications on the solvability of distributionally robust optimization problems in areas such as scheduling which we discuss. We present the Distributionally Robust Max-Flow problem to illustrate our theoretical results.

Revisiting the Marginal Distribution Model: Extensions and Generalizations

October 23, 2017

Talk, Informs Annual Meeting (2017), Houston, Texas

Building on previous work which incorporated the Marginal Distribution Model to examine the persistency problem for discrete optimization, we provide extensions in two ways. Firstly, we extend the distributionally robust problem to now incorporate completely arbitrary marginal distributions, and we find a dual optimization problem that not only points the way to tractable cases but also presents a basic multi-marginal transport problem with a story not unlike that found in the assignment game from mathematical economics. Secondly, we investigate the role of the discrete constraint set’s structure in tractability. As well, we consider how the results generalize/unify some other works.

On the Structure of Cardinality Constrained Assortment Optimization

November 15, 2016

Talk, Informs Annual Meeting (2016), Nashville, Tennessee

Cardinality-Constrained assortment optimization, the problem of offering an assortment of items of constrained size that will maximize expected revenue, is generally regarded as a challenging problem. We provide a new perspective to the structural analysis, one that illuminates the optimality of “greedy solutions.” The approach reinterprets some known results for standard choice models but also provides some new ones as well.