In markets where customers tend to purchase baskets of products rather than single products, assortment optimization is a major challenge for retailers. Removing a product from a retailer's assortment can result in a severe drop in aggregate demand if this product is a complement to other products. Therefore, accounting for the complementarity effect is essential when making assortment decisions. In this paper, we develop a modeling framework designed to address this problem. We model customers' choices using a Markov random field -- in particular, the Ising model -- which captures pairwise demand dependencies as well as the individual attractiveness of each product. Using the Ising model allows us to leverage existing methodologies for various purposes including parameter estimation and efficient simulation of customer choices. We formulate the assortment optimization problem under this model and show that it is APX-hard. We also provide multiple theoretical insights into the structure of the optimal assortments based on the graphical representation of the Ising model, and propose several heuristic algorithms that can be used to obtain high-quality solutions to the assortment optimization problem. Our numerical analysis demonstrates that the developed simulated annealing procedure leads to an expected profit gain of 15% compared to offering an unoptimized assortment (where all products are included) and around 5% compared to using a revenue-ordered heuristic algorithm.

翻译：在顾客倾向于购买商品组合而非单一商品的市场中，商品组合优化是零售商面临的主要挑战。若从零售商的商品组合中移除某一产品，而该产品与其他产品存在互补关系，则可能导致总需求大幅下降。因此，在制定商品组合决策时，考虑互补效应至关重要。本文开发了一个旨在解决此问题的建模框架。我们采用马尔可夫随机场——特别是伊辛模型——来模拟顾客的选择行为，该模型能够捕捉成对需求依赖性以及各产品的个体吸引力。利用伊辛模型使我们能够借助现有方法进行参数估计和顾客选择的高效模拟等多种用途。我们基于该模型构建了商品组合优化问题，并证明该问题是APX难的。此外，我们基于伊辛模型的图表示形式，对最优商品组合的结构提出了多项理论见解，并提出了几种启发式算法，可用于获得商品组合优化问题的高质量解。数值分析表明，与提供未优化的商品组合（包含所有产品）相比，所开发的模拟退火程序可实现15%的预期利润增长；与使用收益排序启发式算法相比，利润增长约为5%。