Assortment optimization with visibility constraints

• 成果类型: Article; Early Access
• 署名作者: Barre, Theo; El Housni, Omar; Brahim, Marouane Ibn; Lodi, Andrea; Segev, Danny
• 署名单位: University of California System; University of California Berkeley; Cornell University; Technion Israel Institute of Technology; Tel Aviv University; Tel Aviv University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02238-9
• 发表日期: 2025
• 关键词: MULTINOMIAL LOGIT MODEL; choice model; approximation

摘要

Motivated by applications in e-retail and online advertising, we study the problem of assortment optimization under visibility constraints (APV). Here, we are given a universe of substitutable products and a stream of customers. The objective is to determine the optimal assortment of products to offer to each customer in order to maximize the total expected revenue, subject to exogenously-given visibility constraints, stating that each product should be shown to a minimum number of customers. We assume that customer choices follow a Multinomial Logit model (MNL). We provide a structural characterization of optimal assortments and present a linear time algorithm for solving APV. To this end, we introduce a novel function called the expanded revenue of an assortment and establish its supermodularity; our algorithm takes advantage of this structural property. Additionally, we prove that APV can be formulated as a compact linear program. Next, we consider APV with cardinality constraints, which limit the maximum number of products that can be included in an assortment. We prove this problem to be strongly NP-hard and not admitting a Fully Polynomial Time Approximation Scheme (FPTAS), even when all products have identical prices. Subsequently, we devise a Polynomial Time Approximation Scheme (PTAS) for APV under cardinality constraints with identical prices. We also examine the revenue loss resulting from the enforcement of visibility constraints, comparing it to the unconstrained problem. To offset this loss, we propose a novel strategy to distribute the loss incurred among the products subject to visibility constraints, charging each vendor an amount proportional to their product's contribution to the revenue loss.