Near-Optimal Algorithms for Capacity Constrained Assortment Optimization
Near-Optimal Algorithms for Capacity Constrained Assortment Optimization
复制标题
容量受限分类优化的近最优算法
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Jiawei Zhang
中科院分区：
文献类型：
--
作者：
Antoine Désir;Vineet Goyal;Jiawei Zhang
分类优化是零售和在线广告等许多实际应用中出现的一个重要问题。在分类优化问题中，目标是在存在由选择模型指定的消费者替代行为的情况下，选择一个使期望收入最大化的商品子集。本文在多项logit （MNL）、嵌套logit （NL）和混合多项logit （MMNL）模型下，研究了容量约束下的分类优化问题。目标是选择总重量或总容量不超过给定范围的物品的收益最大化子集。当混合或巢的数量一定时，我们给出了这些模型的全多项式时间近似方案（FPTAS）。我们的FPTAS使用了类似于解决背包问题的FPTAS的想法。算法的运行时间与MMNL模型中混合物的数量呈指数关系。令人惊讶的是，对于MMNL选择模型的任何近最优算法，对混合物数量的指数依赖是必要的。特别地，我们证明了在一般MMNL模型上，对于任何δ > 0，即使是无约束分类优化，也没有任何具有项目数n和混合物K的运行时间多项式的算法获得比O（1/K1−δ）更好的近似。我们的约简提供了一个过程，为MMNL上的分类优化问题构建一组自然的硬基准实例，这些实例可能具有独立的兴趣。这些实例非常类似于基于考虑集的模型（Jagabathula和Rusmevichientong(2014)），其中考虑集来自图形模型。我们还给出了MMNL和NL模型的一些特殊情况，在这些情况下，我们可以得到一个多项式依赖于混合物数量的FPTAS。
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 consider the capacity constrained version of the assortment optimization problem under several choice models including Multinomial logit (MNL), Nested Logit (NL) and the mixture of Multinomial logit (MMNL) models. The goal is to select a revenue maximizing subset of items with total weight or capacity at most a given bound. We present a fully polynomial time approximation scheme (FPTAS) for these models when the number of mixtures or nests is constant. Our FPTAS uses ideas similar to the FPTAS for the knapsack problem.The running time of our algorithm depends exponentially on the number of mixtures in the MMNL model. We show that surprisingly the exponential dependence on the number of mixtures is necessary for any near-optimal algorithm for the MMNL choice model. In particular, we show that there is no algorithm with running time polynomial in the number of items, n and mixtures, K that obtains an approximation better than O(1/K1−δ) for any δ > 0 for even the unconstrained assortment optimization over a general MMNL model. Our reduction provides a procedure to construct a natural family of hard benchmark instances for the assortment optimization problem over MMNL that may be of independent interest. These instances are quite analogous to the consideration set based models (Jagabathula and Rusmevichientong (2014)) where the consideration set arises from a graphical model. We also present some special cases of MMNL and NL models where we can obtain an FPTAS with a polynomial dependence on the number of mixtures.