Talks and presentations

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.