Assortment Optimization Under History-Dependent Effects

• 成果类型: Article; Early Access
• 署名作者: He, Taotao; Zhang, Yating; Zheng, Huan
• 署名单位: Shanghai Jiao Tong University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.1273
• 发表日期: 2026-07-08
• 关键词: choice model; satiation; mixed-integer nonlinear programming; perspective formulation; convex extension; cyclic policy; choice model; PROGRAMS; convex; management; ENVELOPES; SPARSE; chain

摘要

This paper examines how to plan multiperiod assortments when customer utility depends on historical assortments. We formulate this problem as a nonlinear integer programming model and show it is NP-hard in the presence of a negative historydependent effect (such as a satiation effect). We build solution methodologies for obtaining global optimal solutions under a general setting where the history-dependent effects could be a mixture of positive and negative. We propose using a lifting-based framework to reformulate the problem as a mixed-integer exponential cone program that state-of-the-art solvers can solve. We also design a sequential revenue-ordered policy and show that it solves our problem to optimality in polynomial time when historical assortments positively affect customer utility (such as an addiction effect). Additionally, we identify an optimal cyclic policy for an asymptotic regime, and we also relate its length to the customer's memory length. Finally, we present a case study using a catering service data set, showing that our model demonstrates good fitness and can effectively balance variety and revenue.