Assortment Optimization Under History-Dependent Effects

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 history-dependent 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.

Funding: H. Zheng’s work was supported by the National Natural Science Foundation of China [Grants 72325003 and 72221001]. T. He’s work was supported by the National Natural Science Foundation of China [Grants 72101146 and 72331006]. Y. Zhang’s work was supported by the National Natural Science Foundation of China [Grants 72231003].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2024.1273.