Posts by Collection

portfolio

publications

On the Structure of Cardinality-Constrained Assortment Optimization

Published in , 2017

We study the static assortment optimization problem with cardinality constraints, i.e., the problem of offering an assortment of items of constrained size that will maximize expected revenue. This is generally regarded as a challenging problem, with identified hardness results in the existing literature for a number of popular and/or well-studied choice models. Motivated by existing approaches in the unconstrained setting that find successful exploitation of identified structure to devise either exact or approximate solution methods, we introduce another structural property of possible interest for study in the cardinality constrained setting. Recently, the work of Jagabathula (2016) has identified the optimality of a local search method for the cardinality constrained static assortment problem under Multinomial Logit (MNL) Choice, making MNL a rare case study of tractability among cardinality constrained problems. So we first revisit the MNL constrained assortment problem under a new lens in search of structure that explains its “tractability.” Following this, we study the extent to which this property holds in other choice models. Indeed, we find that local search is optimal for some other choice models, and remains so even under more generalized cardinality constraints. Finally, we provide and test some algorithms (which require black-box access to the expected revenue function) that can be applied to the joint assortment and pricing problem under certain choice models, showing favorable performance small to moderate-sized problems against some current approaches.

Recommended citation: Louis Chen, David Simchi-Levi. (2017). "On the Structure of Cardinality-Constrained Assortment Optimization." https://www.dropbox.com/s/tbpw3ig9vzrl3xw/AssortmentPaper.pdf?dl=0

Distributionally Robust Linear and Discrete Optimization with Marginals

Published in Revise and Resubmit (Operations Research), 2018

In this paper, 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 generalize the primal-dual formulations for this problem from the set of joint distributions with absolutely continuous marginal distributions to arbitrary marginal distributions using techniques from optimal transport theory. While the robust bound is shown to be NP-hard to compute for linear optimization problems, 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.

Recommended citation: Louis Chen, Will Ma, Karthik Natarajan, David Simchi-Levi, Zhenzhen Yan. (2018). "Distributionally Robust Linear and Discrete Optimization with Marginals." Revise and Resubmit (Operations Research). https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3159473

Distributionally Robust Max Flows with Marginals

Published in In preparation, to be submitted, 2018

Consider an s-t flow network in which the arc capacities are distributed according to an unknown distribution, but with known marginals. We study the problem of finding a coupling of the marginals that yields the worst, expected Max-flow value. Towards solving this optimization problem, we identify a primal-dual formulation. As one might expect, the form relates to the well-known Max Flow, Min-Cut theorem. And this leads to the rather 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. Our contributions in this talk are twofold: (1) we present a linear program (that is efficient with finite-supported marginals) that not only computes the worst-case expected value but is of a form amenable in a two-stage network design formulation, and (2) we show that the problem of finding the worst-case coupling of the stochastic arc capacities boils down to finding an optimal distribution over the set of s-t cuts, which we show can be found efficiently.

Recommended citation: Louis Chen, Will Ma, James Orlin, David Simchi-Levi. (2018). "Distributionally Robust Max Flows with Marginals." In preparation, to be submitted. 1(2). https://www.dropbox.com/s/k6dsmnq7h803v8n/DROMaxFlows.pdf?dl=0

talks

On the Structure of Cardinality Constrained Assortment Optimization

Published:

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.

Revisiting the Marginal Distribution Model: Extensions and Generalizations

Published:

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.

Distributionally Robust Linear and Discrete Optimization with Marginals

Published:

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.

teaching

Introduction to Operations Management

MBA course (15.761), MIT Sloan School of Management, 2014

Taught by Professor Tauhid Zaman. This course was part of the MIT Leaders for Global Operations (LGO) curriculum, in which my TA responsibilities included running recitation sessions and doing homework/report grading.

Statistical Thinking and Data Analysis

Undergraduate course (15.075), MIT Sloan School of Management, 2014

Taught by Professor Hoda Bidkhori. My TA responsibilities included running recitation sessions and doing homework/report grading.

Manufacturing System and Supply Chain Design

MBA course (15.763), MIT Sloan School of Management, 2016

Taught by Professors David Simchi-Levi, Don Rosenfield. My TA responsibilities included running recitation sessions and doing homework/report grading