A Tractable Consideration Set Structure for Network Revenue Management
A Tractable Consideration Set Structure for Network Revenue Management
复制标题
网络收益管理的易于处理的考虑因素集结构
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
K. Talluri
中科院分区：
文献类型：
--
作者：
A. Strauss;K. Talluri
模型结合更现实的客户行为模型，客户从一个报价集选择，最近已经成为流行的品种优化和收益管理。这些模型的动态规划是棘手的，近似的确定性线性规划称为CDLP，它具有指数数量的列。当有多个客户考虑购买的产品时，CDLP很难解决，因为列生成是NP难的。然而，最近的研究表明，制定的基础上段与削减强加的一致性（SDCP+）是易于处理的，非常接近的CDLP值。在本文中，我们调查的结构的考虑集，使这两个配方完全相同。我们表明，如果段考虑集遵循树结构，CDLP = SDCP+。我们给出了一个反例，表明周期可以诱导CDLP和SDCP+弛豫之间的间隙。我们推导出两类有效的不等式称为流和同步不等式，以进一步改善（SDCP+），在考虑集结构的循环的基础上。我们给出了一个数值研究，显示这些基于周期的切割的性能。
Models incorporating more realistic models of customer behavior, as customers choosing from an offer set, have recently become popular in assortment optimization and revenue management. The dynamic program for these models is intractable and approximated by a deterministic linear program called the CDLP which has an exponential number of columns. When there are products that are being considered for purchase by more than one customer segment, CDLP is difficult to solve since column generation is known to be NP-hard. However, recent research indicates that a formulation based on segments with cuts imposing consistency (SDCP+) is tractable and approximates the CDLP value very closely. In this paper we investigate the structure of the consideration sets that make the two formulations exactly equal. We show that if the segment consideration sets follow a tree structure, CDLP = SDCP+. We give a counterexample to show that cycles can induce a gap between the CDLP and the SDCP+ relaxation. We derive two classes of valid inequalities called flow and synchronization inequalities to further improve (SDCP+), based on cycles in the consideration set structure. We give a numeric study showing the performance of these cycle-based cuts.