Mitigating Choice Model Ambiguity: A General Framework and its Application to Assortment Optimization

In several application domains, discrete choice models have become a popular tool to accurately predict complex choice behavior within the classical predict-then-optimize paradigm. Due to a variety of possible error sources, however, estimated choice models may be subject to ambiguity, which may induce different optimal decisions of highly varying quality. While previous studies focused on … Read more

An Exact Method for Assortment Optimization under the Nested Logit Model

We study the problem of finding an optimal assortment of products maximizing the expected revenue, in which customer preferences are modeled using a Nested Logit choice model. This problem is known to be polynomially solvable in a specific case and NP-hard otherwise, with only approximation algorithms existing in the literature. For the NP-hard cases, we … Read more

An algorithm for assortment optimization under parametric discrete choice models

This work concerns the assortment optimization problem that refers to selecting a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a parametric choice model. The key challenge lies in the computational difficulty of finding the best subset solution, which often requires exhaustive search. The … Read more

Constrained Assortment Optimization under the Paired Combinatorial Logit Model

We study the assortment optimization problem when customer choices are governed by the paired combinatorial logit model. We study unconstrained, capacitated and knapsack constrained versions of this problem, which are all known to be NP-hard. We design efficient algorithms that compute approximately optimal solutions, using a novel relation to the maximum directed cut problem and … Read more

Submodularity in conic quadratic mixed 0-1 optimization

We describe strong convex valid inequalities for conic quadratic mixed 0-1 optimization. These inequalities can be utilized for solving numerous practical nonlinear discrete optimization problems from value-at-risk minimization to queueing system design, from robust interdiction to assortment optimization through appropriate conic quadratic mixed 0-1 relaxations. The inequalities exploit the submodularity of the binary restrictions and … Read more

Near-Optimal Algorithms for Capacity Constrained Assortment Optimization

Assortment optimization is an important problem that arises in many practical applications such as retailing and online advertising. In an assortment optimization problem, the goal is to select a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a choice model. In this paper, we … Read more

A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined Into One

In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the … Read more