昆明网站建设公司_,营销方案有哪些,个人网站可以备案几个,百度网站怎么做友情链接摘要
受租赁服务在电子商务中的应用的激励#xff0c;我们考虑为不同类型的到达消费者提供可重复使用资源的在线分类的收入最大化。我们针对贝叶斯环境中的最优在线策略设计了具有竞争力的在线算法#xff0c;其中类型随时间独立于已知的异构分布绘制。在初始库存最小值cmin…摘要
受租赁服务在电子商务中的应用的激励我们考虑为不同类型的到达消费者提供可重复使用资源的在线分类的收入最大化。我们针对贝叶斯环境中的最优在线策略设计了具有竞争力的在线算法其中类型随时间独立于已知的异构分布绘制。在初始库存最小值cmin较大的情况下我们的主要结果是对于可重用资源的一般情况近似最优的1−min1 2p logcmin/cmin竞争算法。我们的算法依赖于问题的预期LP基准解决该LP并通过独立的随机舍入模拟解决方案。主要挑战是从这些基于仿真的算法中以计算效率高的方式获得逐点库存可行性。为此我们使用几个技术要素来设计丢弃策略——每个资源一个。这些策略处理可重用性下的库存可行性和每个资源的收入损失之间的权衡。然而丢弃一个资源单元会改变其他资源的未来消耗。为了应对这一新挑战我们还引入了后处理分类程序以帮助设计和分析并行运行的丢弃策略这可能是独立的兴趣所在。作为一个副作用通过利用先知不等式文献中的技术我们进一步展示了针对不可重用资源的特殊情况的改进的近最优1−1/√cmin3竞争算法。最后我们使用对合成数据的数值模拟来评估我们算法的性能。
1引言
产品组合规划是指收入最大化的公司决定向消费者展示哪一部分产品。在经典零售应用中重点主要是销售然而随着在线电子商务平台的出现一些应用程序出现了其重点是出租可重用资源。可重复使用的资源也称为租赁产品在分配给消费者后会在一段时间内离开库存一旦重新分配给新的消费者。例如AWS等云计算平台中的虚拟机Airbnb等度假租赁在线市场中的房屋以及本地Thumbtack等在线劳动平台的专业服务。为了获取更多收入一旦新消费者与平台交互个性化分类策略可以决定显示这些资源的不同子集这种策略的任务是在给定库存限制的情况下长期管理产品组合的顺序。 受上述应用的激励我们研究了可重用资源的在线分类其中平台顺序地为到达的消费者流做出不可撤销的分类决策。 每个消费者都有一种类型该类型决定了她在给定每个可能的产品组合时的选择概率——称为消费者的选择模型。该平台在消费者每次租用产品时收取一次性个性化付款。不同的产品有不同的租金这取决于消费者的类型。为了对租赁期限的不确定性进行建模我们考虑了一个随机模型其中每次租赁产品时租赁期限都是独立绘制的。 到达消费者的类型也决定了不同产品的租赁期限分布。为了对平台关于其未来消费者的先前信息进行建模我们采用贝叶斯方法这些信息通常是基于在线平台中过去消费者的数据形成的。我们假设随着时间的推移这些类型是从已知的异构分布中独立绘制的。 一旦新消费者到达平台会从已知的类型分布中观察其已实现的类型显示新的产品子集并允许消费者根据其选择模型从该子集随机选择产品。目标是设计一种在线分类算法以便在决策期内最大化预期收取的总租金也称为收入。重要的是我们考虑每个产品都有初始库存的情况并且算法应该始终对可用的产品子集进行分类。可用性取决于产品的当前库存水平——数量随着租赁产品的单位而减少随着返回库存而增加。 给定整个决策层的分布序列我们问题中的收益基准是任何可行的在线算法作为平台的预期收益的上限其中预期超过了算法、类型序列和消费者选择的随机性。我们使用竞争比率的概念来衡量在线算法的性能即在线算法的预期收益与目标收益基准之间的最坏情况比率。 正如在分类优化的文献和实践中常见的那样我们假设一般的消费者选择模型是弱替代品即对一种新产品进行分类只会微弱地降低另一种分类产品的选择概率见假设1。如果没有进一步的假设即使是一次性分类优化也很难计算。为了解决这个问题我们假设oracle可以访问一个黑箱算法该算法可以解决一次性分类优化见假设3。同样这是文献中的常见假设当考虑一般消费者选择模型时与一次性问题相关的计算问题Golrezaei等人2014Rusmevichientong等人2020。在oracle访问计算模型中我们的目标是针对我们的问题设计多项式时间竞争在线算法以获得适当的收益基准。 在这种情况下找到使预期总收入最大化的最佳在线策略的问题纯粹是计算问题指数大小的动态规划DP可以制定最佳在线策略。虽然在我们的问题中没有正式的计算难度来计算最佳在线策略但据推测即使在oracle访问模型中计算难度也很高。1因此很自然地将最佳在线策略的预期收益作为收益基准并研究其是否适用于多项式时间竞争在线算法。 更具体地说我们在本文中提出了以下问题在预期收益方面多项式时间在线算法与最优在线策略有多接近特别是我们能否获得与最优在线策略相关的恒定或接近最优的竞争在线算法当初始库存较大时 Rusmevichientong等人2020的研究结果是在为上述问题提供令人信服的答案方面取得的一项重大进展该研究为指数大小的最佳在线DP建立了近似动态规划方法。他们表明使用最优收益函数线性近似的贪婪算法至少获得最优在线预期收益的12。他们进一步研究了租赁期限无限长即资源不可重复使用且租赁费用类型独立的情况。在此设置中他们展示了如何执行简单静态策略的推广以获得最佳在线策略预期收入的1−min1 21 3√cmin分数其中cmin是不同产品的最小初始库存。2当初始库存较大且资源不可重复使用时最后一个结果基本上是一个接近最优的竞争算法。注意大的初始库存制度在分类优化的许多应用中都是相关的这也是我们论文的主要焦点 注释 1.例如参见帕帕季米特里乌和Tsitsiklis1987了解在部分可观察的马尔可夫决策过程中找到最优策略的PSPACE公司难度以及Rusmevichientong公司等人2020和阿纳里等人2019中的相关讨论。 2.如果租赁费取决于类型Rusmevichientong公司等人2020表明相同的政策获得了1−最小值1 2R 3√cm的竞争性比率保证其中R是不同类型的最高和最低租赁费之间的比率。
1.1本文贡献 本文的主要贡献是以下结果。 主要结果对于可重用资源的贝叶斯在线分类的一般情况我们提出了一种多项式时间在线算法该算法获得了1−min的近似最优竞争比 即使租赁费用、消费者选择和租赁期限分布因类型而异并且在不同类型之间任意变化上述竞争性比率保证仍然有效。 为了获得上述结果我们的工作与Rusmevichientong等人2020的不同之处在于考虑了不同的收入基准。特别地我们考虑最优在线策略的线性规划松弛称为贝叶斯期望LP。为了定义这个基准假设一个可行的在线政策知道未来类型的确切实现但不知道消费者选择和租赁期限的实现。最佳的此类政策被称为千里眼最佳在线政策显然提供了一个收入基准。现在考虑放宽这一政策只要求可重复使用资源的库存可行性约束在类型、消费者选择和租赁期限的随机性上保持预期。给定类型分布序列该松弛由具有指数数量变量和多项式数量时变包装约束的LP编码以确保可重用资源在预期中的库存可行性。详见第2.2节。 事实证明我们可以简单地在多项式时间内求解贝叶斯期望LP方法是使用椭圆体方法求解其对偶程序——给定离线分类预言机的访问权限。给定LP解贝叶斯在线优化中一种简单但强大的技术是使用基于模拟的舍入算法来模拟该LP的最优解有关此方法的示例请参阅Alaei等人2012、Devanur等人2012、Ma等人2018、Gallego等人2016、Wang等人2018、Dickerson等人2018、Baek和Ma 2019。在观察到到达消费者的类型后该算法从LP解决方案中的产品子集的分布中独立地对分类进行采样忽略库存约束。与LP解决方案相比该算法在预期收益方面没有损失然而它只考虑预期中每种产品的库存约束而不一定在现有随机性的每个样本路径下。 我们的主要技术贡献是提供在多项式时间内将基于模拟的算法转换为逐点可行的在线算法的技术在预期收益中具有恒定或可忽略的乘法损失。为此我们在一段时间内运行一个单独的过程每个产品一个以及基于模拟的策略。在每次对产品分类进行抽样后每个程序决定是否丢弃相应的产品如果该产品在抽样子集中以保持该产品的库存可行性。根据LP解决方案进行采样然后使用产品特定丢弃规则的这种特定架构在过去已经过探索例如参见Alaei等人2012、Gallego等人2016、Wang等人2018、Dickerson等人2018年、Baek和Ma2019。3(注释3具体参见Gallego等人2016年第7节中的“原始路由算法”和Wang等人2018年第4.2节的“分离算法”。)同样我们的目标是设计多项式时间在线丢弃策略和其他必要的算法构造处理维持库存可行性和放弃每个产品的收入损失之间的权衡。针对我们问题的主要新挑战是i产品是可重复使用的ii产品是弱替代品因此丢弃产品会增加其他产品的选择概率以及iii丢弃可能是随机的-这与可重用性相结合在时间上的选择指标随机变量之间创建了复杂的相关结构并使关于策略的逐点可行性的争论具有挑战性。在下文中我们概述了我们的主要技术贡献以及他们如何克服这些挑战。 一 一般租赁期限分布/近似最优丢弃第3.2节近似最优丢弃程序背后的主要思想是以小概率随机丢弃每个可用的样本产品。这是一种简单而合理的方法参见Hajiaghayi等人2007因为基于模拟的算法考虑了预期中每种产品的库存约束。通过概率γ0的独立随机丢弃我们通过确保出租产品的单位数量的预期值在任何时候最多为其初始库存量的1−γ倍在库存可行性约束中留有一定的余地。如果该数量作为独立租金指标随机变量的总和集中在其期望值附近那么当γO p logcmin/cmin时我们将以高概率避免违反库存约束。此外它只损失了该产品预期收入的γ部分。 然而上述简单方法不能如所描述的那样工作因为i资源是可重用的并且库存是有限的因此如果时间τ的租赁持续时间至少为t−τ并且产品的最后一个单位在τ处租赁则产品在某个时间τt处的租赁指标随机变量可以与同一产品在时间t处的租金指标随机变量相关联4 注释4我们想强调的是在我们的论文出现在线版本后通过与Goyal等人2020a的作者的个人沟通我们被告知这篇论文当时在线上没有独立并同时发现了一种类似于我们的子分类采样的程序用于具有对抗性到达和可重复使用资源的设置。 ii一旦丢弃程序将产品从抽样分类中删除其他产品的同类产品将减少因为消费者的选择是较弱的替代品。这反过来又增加了到达消费者选择其他产品的可能性因此与基于模拟的算法的预期数量相比所得到的算法将增加未来租赁的不同产品的预期数量。 我们通过在独立随机丢弃之后提出后处理步骤来解决上述问题我们称之为子分类采样。简言之子分类抽样的目标是找到可用子集上的分布以便不会丢弃的产品将以与贝叶斯期望LP的最优解完全相同的概率出租。甚至还不清楚这种分布是否存在然而我们证明了这一点并提供了一个多项式时间结构来从这个分布中采样。利用子分类抽样的财产我们提出了一种耦合技巧以显示我们期望的浓度尽管事实上租金指标随机变量在时间上是相关的。请注意子分类抽样的任务很一般在其他应用中可能具有独立的利益。4(注释4我们想强调的是在我们的论文出现在线版本后通过与Goyal等人2020a的作者的个人沟通我们被告知这篇论文当时在线上没有独立并同时发现了一种类似于我们的子分类采样的程序用于具有对抗性到达和可重复使用资源的设置。) II一般租赁期限分布/1 2-竞争性丢弃第3.3节作为可重复使用资源的一般情况的替代丢弃策略考虑一个指数大小的DP它跟踪产品的每个单元的状态即当每个单元返回库存时并最优地解决丢弃任务。我们介绍了这个DP的近似版本我们也称之为乐观DP可以在多项式时间内解决。我们的目标是当我们每次做出丢弃决定时通过外部过程自动补充库存时使产品的单位收入最大化从而使产品的整个库存始终可用。这种新的DP与库存无关因此是多项式大小。然后我们考虑一个丢弃算法该算法做出与乐观DP相同的决策。结果是一个非自适应阈值丢弃规则即只有当可用产品的租金低于某个阈值时才丢弃该可用产品。这些阈值是预先计算的仅取决于产品、时间和实现的类型。 为什么上述丢弃算法是合理的近似其主要直觉如下。我们可以证明该算法的预期收益是库存水平的凹函数即库存水平越高单位预期收益越低。 因此当实际没有补充时它获得的单位收入至少与补充后的DP相同。然后我们使用“因子揭示线性规划”及其对偶分析该独立于库存的DP的价值与预期LP的单位收入之间的最坏情况比率。该方法为该比率确定了12的下限。 值得注意的是基于双重拟合的类似证明技术已在文献中用于不可重复使用资源的其他问题例如见Zhang和Adelman 2009Adelman 2007Alaei等人2012Gallego等人2016Wang等人2018。我们的工作扩展了现有分析以证明在资源可重用时基于LP的丢弃策略的性能保证。 我们强调在给定预期LP解决方案的情况下我们设计上述近似丢弃策略的DP与Rusmevichientong等人2020中的近似动态规划方法具有相似但不完全相同的递归结构用于直接近似最优在线策略事实上与他们的方法不同我们DP的Bellman更新方程使用了预期LP最佳分类抽样概率的解。因此虽然两个DP提供了相同的近似因子12但我们的是预期LP的更强基准而他们的是最佳在线策略。这个微妙的结果证明差异是将第3.2节和第3.3节中两种算法的性能保证结合起来的关键以便获得一种简单的混合算法相对于更强的预期LP基准实现理论上的“两全其美”竞争比率保证正如我们后来观察到的在数值模拟中提高了性能。 三 基于仿真的混合算法第3.4节通过不同的丢弃规则访问上述基于仿真的算法我们的目标是定义一种混合算法该算法可以享受小库存和大库存的竞争比率。为此我们预先决定每个产品使用哪种丢弃策略。特别是我们分别使用每个产品的乐观DP的价值函数来计算该产品遵循乐观DP的预期收入与该产品对预期LP目标的贡献之间的比率Ri。然后我们将该比率与1-εci函数ε·的定义见1进行比较以将产品划分为大库存即当Riεci1时和小库存即Riε*ci1时。对于每个大库存产品我们在第3.2节中运行随机丢弃策略对于每个小库存产品在第3.3节中运行乐观DP丢弃策略。我们还使用子分类抽样程序进行后处理以纠正由于替代性较弱而导致的非废弃产品选择概率的增加。通过使用以下事实i两种算法的竞争比率分析在产品之间解耦ii两种分析将从每种产品获得的预期收入与该产品对预期LP目标的贡献进行比较以及iii子分类抽样校正了未丢弃产品的选择概率我们展示了由此产生的混合策略结合了两种竞争比率5 注释5值得注意的是Rusmevichientong等人2020的12竞争近似DP算法不能使用该方法与我们的近似最优丢弃策略相结合因为该近似DP算法与最优在线策略竞争而不是与预期LP竞争。 虽然这种混合算法实现了1−min的两个世界的最佳竞争比在实际情况下它也可能优于这两种政策第4节中的数值模拟结果从经验上支持了这一主张。我们还提出了使用条件期望方法的第二种混合算法。详见第3.4节。 我们还通过考虑不可重用资源的特殊情况来补充我们的结果。通过利用来自先知不等式文献的杠杆老化技术并将其扩展到贝叶斯分类优化问题我们提供了在这种情况下相对于预期LP的1−1√cmin3的近似最优改进竞争比。更多详情请参见第EC.1节和第EC.5节。
iii数值模拟第4节 我们最终为拟议政策的收入表现提供了数字依据。根据Golrezaei等人2014年和Rusmevichientong等人2020年的数字实验设置我们将我们提出的政策即混合算法和无限租赁期限下最优丢弃的模拟的收入与文献中的其他政策进行了比较。在我们的数值模拟中我们考虑了一般租赁期限分布和无限租赁期限的情景。在所有这些情况下我们的政策在预期收入方面明显优于其他政策。 1.2进一步相关工作 近几十年来收入管理产品组合规划的文献越来越多。我们让读者参考相关的调查和书籍参见K–ok等人2008年兰开斯特1990年何和唐1998年进行全面研究。van Ryzin和Mahajan1999研究了静态模型该模型在多项logit消费者选择模型下捕捉了库存成本和产品种类之间的权衡。后来的工作考虑了各种消费者选择模型下的分类例如需求替代模型Smith和Agrawal 2000、多项logit模型Talluri和van Ryzin 2004Gallego等人2004Liu和van Ryjin 2008Topaloglu 2013、兰开斯特选择模型Gaur和Honhon 2006、排名列表偏好Honhon等人2010Goyal等人2016Aoud等人2018、然后考虑选择模型Aouad等人2020和非参数数据驱动选择模型Farias等人2013。 最近在先前的自由/对抗和贝叶斯设置下对在线分类进行了研究。对于不可重复使用的产品Bernstein等人2015研究了两种产品的模型即消费者类型和泊松到达率。Chan和Farias2009研究了一个具有非平稳消费者类型的模型并展示了与千里眼最佳在线基准相关的12个性能保证。Golrezaei等人2014年引入了“库存平衡”算法——灵感来自Mehta等人2005年对在线广告分配的开创性工作——并使用原始对偶方法分析了它们在先前免费设置下的性能保证。Ma和Simchi Levi2020后来对这一分析进行了改进和推广。Chen等人2016考虑了另一种变体其中产品组合以折扣价格作为附加产品提供。本文还使用了丢弃以确保逐点库存可行性的思想由于产品替代它们面临着类似的挑战。为了克服这一挑战作者引入了一种针对特定目标的误差抽样程序。相比之下我们的分类抽样不会产生任何错误可以用于更一般的目的。 对于可重复使用产品的在线分类Levi和Radovanovi c2010研究了一个模型该模型假设产品之间存在独立需求而无限销售范围内的客户没有任何选择行为。Owen和Simchi Levi2018的后续工作扩展了这项工作以纳入客户选择行为和有限的销售范围。Chen等人2017研究了单个可重复使用产品的多个单元的模型。他们考虑了随机使用持续时间和提前预订并获得了与数据相关的性能保证当产品库存和客户到达率以相同的速度线性增长时这些性能保证是渐近最优的。 最后Rusmevichientong等人2020研究了贝叶斯设置和Gong等人2021Feng等人2019年、2021、Goyal等人2020b研究了无先验/对抗性环境其中租金和租期分布都是类型相关的并且在不同时间段内是相同的。 在贝叶斯环境中我们的问题类似于“先知不等式”问题的某些方面。这一问题起源于Krengel和Sucheston1978在70年代的开创性工作并已被广泛研究。文献中也研究了这个问题的组合推广。例如拟阵的预言不等式Samuel Cahn等人1984年Hajiaghayi等人2007年Kleinberg和Weinberg 2012年、匹配Alaei等人2012年和组合拍卖D–uetting等人2017年。在这些概括中用于计算最佳在线策略的自然动态规划是指数大小的Niazadeh et al.2018Anari et al.2019与我们的问题类似。参见Lucier2017了解全面调查。 我们的一些技术类似于先知不等式匹配Alaei et al.2012、魔术师问题和在线争用解决方案Alaei2014、Brubach et al.2021、Feldman et al.2016、静态日历定价问题Ma et al.2018、可重用离线节点的在线二部匹配Dickerson et al.2018、以及志愿者众包问题Manshadi和Rodilitz 2022。与我们最接近的是Baek和Ma 2019针对可重复使用资源的网络收入管理问题的研究在该研究中作者们独立地同时发现了类似于我们针对小库存机制的算法的策略。 其他预期的LP基准在文献中以“事前放松”的名义用于各种随机在线优化和机构设计问题。例如参见Alaei等人2012、D¨uetting等人2017、Lee和Singla2018、Vera和Banerjee2021、Ma等人2018和Anari等人2019。我们用于分析基于DP的阈值丢弃规则的因子揭示技术类似于Adelman2007的LP方法、Alaei2014、Wang等人2018中的双重拟合方法以及用于近似动态规划的其他基于LP的方法参见Si等人2004的综合研究。 我们的一些技术类似于先知不等式匹配Alaei等人。 2012年、魔术师的问题Alaei 2014、静态日历定价问题Ma等人。 2018该研究还研究了没有可重用资源的静态分类策略和志愿者众包问题Manshadi和Rodilitz 2022。与我们的贝叶斯预期LP相似其他预期LP基准在文献中以“事前放松”的名义用于各种随机在线优化和机构设计问题。例如参见Alaei等人。 2012Devanur等人2012、Feldman等人2016、D¨uetting等人2017、Chawla等人2017年、Lee和Singla2018年、Vera和Banerjee2021、Ma等人2018、Anari等人2019年、Dickerson等人2018年。 另一项与我们相关的有趣工作是维拉和巴纳吉2021以及巴纳吉和弗伦德2020年的工作。这里的目标是获得改进的基于附加或遗憾的近似值具有包装约束的各种随机在线优化问题。这些论文与我们的不同之处在于采用了不同的技术方法并考虑了不同的制度即当库存随地平线增加时然而将他们的技术应用于可重用资源问题是一个有趣的未来研究方向。
2 准备工作
我们首先将问题、模型和第2.1节中的所有必要假设形式化。然后我们在第2.2节中简要解释了预期LP基准的各个方面。 2.1模型和问题定义 该平台提供n种不同的租赁产品按[n]{12…n}索引。每个租赁产品i具有ci∈Z的初始库存。有兴趣租用这些产品的消费者在时间t1、2、…、。T.消费者T具有类型zt∈zt其中zt表示时间T时可能类型的离散空间。我们假设类型是独立于已知概率分布Ft:zt绘制的→ [01]在时间t1。T 当消费者t到达时她的类型zt向平台展示。给定该类型和截至时间t的历史平台从其库存中提供可用产品的分类St∈S其中S⊆2[n]是可提供的所有可行分类的集合忽略库存可用性。给定种类St消费者选择一个租赁产品它∈St向平台支付租赁费并在随机租赁期限dt∈Z内保留该产品。 我们考虑了消费者选择行为、不同产品的租赁费用和不同产品的租金持续时间分布取决于每个时间t的类型zt的设置。形式上消费者类型z定义为元组⟨zrzGz⟩因此•具有类型z的消费者的选择由通用选择模型函数进行建模→ [01]其中zSi是当提供分类集S∈S时类型为z的消费者选择产品i出租的概率。 •对于类型为z的消费者r zr z 1rz 2…rz n∈r n其中ri z表示产品i的租赁费。此外GzGz 1Gz 2…Gz n其中Gz i表示类型为z产品i的租用期限的c.d.f.。我们使用gi z:[T]→ [01]表示z型产品i的租赁期限的p.d.f。 此外设’Gz i·≜1−Gz i·。 注意我们假设租赁期限在时间上是独立的也就是说如果在时间tz类型的消费者选择了产品i则新的样本dtGz i被实现为该产品的租赁期限。 我们进一步将以下假设应用于我们的选择模型和可行组合这在以前的文献中是常见的参见Golrezaei等人2014Rusmevichientong等人2014假设1弱替代性。对于所有的t∈[t]z∈Zt和i∈[n]⑪z∅i0。此外对于所有的S∈S和j∈[n]/{i} 假设2向下关闭可行性。如果S∈S和S′⊆S则S′∈S即在移除其提供产品的任何子集后可行的分类将保持可行。 备注1。在Airbnb等在线酒店服务中用户在平台向他们展示列表之前会向平台报告他们的入住时间。在这种变化中平台通过使用到达类型的当前租赁时间的准确实现来做出分类决策。 事实上这是我们模型的一个特例其中租赁时间分布是点质量。 给定类型分布FtT T1目标是设计在线算法——扮演平台的角色——最大化从租金中获得的预期收入这里期望是算法如果随机和环境的随机性即类型、消费者选择和租赁期限。该问题的收益基准定义为通过任何可行的在线算法获得的预期收益的任何上限通过可行的在线计算可能实现或可能不实现。固定一个收益基准我们通过与该基准的竞争比率来评估任何在线算法的性能。非正式地说竞争比率是在线算法的预期总收入与基准之间的最坏情况比率其中最坏情况是所有可能的类型分布。 定义1竞争比率。在线算法A与给定revenue基准相比是α-竞争的如果 其中RevA[·]是算法A的预期收入OPT[·]为给定的收入基准。 对于一般的消费者选择模型准确甚至近似的离线分类优化在计算上是困难的K¨ok等人2008。为了在为一般消费者选择模型设计多项式时间在线算法时避免这一障碍我们假设可以使用解决离线分类问题的算法。为了简单起见我们假设整个论文中的解算器是精确的但如果解算器为某个0β1的β近似算法则我们的所有结果仍然适用于竞争比率中β的乘法降级。 假设3离线预言机。对于所有的t∈[t]、z∈Zt和∈R∈R n我们都可以使用oracle访问一个算法该算法可以找到子集S∈S从而 2.2 贝叶斯预期LP基准 根据关于未来不确定性和所需计算能力的给定信息考虑以下收入基准层次 1。最佳离线最佳离线算法的预期收益该算法具有关于已实现类型序列ztT T1的完整信息每种类型zt和产品i的租赁持续时间的精确实现以及每种可能分类的消费者选择的精确实现。 2.Clairvoyant最佳在线最佳在线算法的预期收入该算法具有关于已实现类型序列ztT T1的完整信息但不知道租赁期限的确切实现也不知道消费者的选择。 3.非透视最优在线仅知道类型分布序列的最优在线算法的预期收益FtT T1 图1 比较了这些基准的预期收入。即使资源不可重复使用也不存在针对最佳离线的持续竞争在线算法见第EC2节。最佳非透视在线策略是一个较弱的基准需要解决指数大小的动态规划Rusmevichientong等人2020。Golrezaei等人2014针对不可重复使用的产品提出的在线透视优化Gong等人2021将其扩展到可重复使用产品是预期收入的中间基准此外它必须解决指数大小的动态规划以在给定额外信息{zt}T T1这不提供给正常的在线算法的情况下计算其分类决策。 我们所有算法中的一个关键组成部分是贝叶斯预期LP基准——这是一个概念常用于先前关于在线分配、机制设计和分类优化的文献中以纠正上述基准的问题例如参见Chawla等人2010年、Alaei 2014年、Ma等人2018年、Gallego等人2016年、Wang等人2018年和Anari等人2019年。该基准由预期LP[{Ft}T T1]表示使用线性规划来捕获只需要以满足期望中的库存约束其中期望被视为租赁持续时间和消费者类型的随机性给定类型分布FtT T1 这里变量{yStzt}t∈[t]S∈Szt∈zt对应于给定类型zt被实现时分类S被提供给消费者的概率第一个约束表明库存在预期中的可行性。 首先该LP的最佳目标值是透视最佳在线基准的预期收益上限因此是较弱的非透视最佳在线建议1证据见第EC.3节。第二使用离线分类的预言机可以有效地解决预期的LP[{Ft}T T1]命题2证据见EC.3节。我们在所有算法中使用这个计算块作为预处理步骤。6最后定理1中的近似最优保证表明随着初始库存变为无限最优在线以及透视在线和预期LP[{Ft}T T1]之间的差距缩小到零。 提案1。对于任何类型的分布FtT T1千里眼最佳在线基准的预期总收入由预期LP〔FtT1〕上限。 提案2。给定离线分类的算法假设3可以在时间PolyntP t∈[t]|zt|中有效地计算期望LP[{Ft}t t1]的最优分配{yStzt}。此外{yStzt}不超过PolyntP t∈[t]|zt|个非零条目。 注释6事实上需要使用离线分类求解器作为分离预言器来运行此LP的对偶的椭圆体方法以便找到最优解。在实践中为了获得更快的算法可以使用诸如Vaidya1996之类的切割平面方法或甚至更快的几乎线性时间切割平面方法例如Lee等人2015这些方法更有效地使用分离预言。
3 一般租赁期限的近似最优算法
在本节中我们展示了我们的主要结果——一种基于在线模拟的近似最优算法其竞争比至少为最大 1 设γ*cmin为方程1中γ的最佳赋值。不难验证ε*cminO p logcmin。我们首先在第3.1节中概述了我们的方法。然后我们在第3.2节中引入了竞争比率为1-ε*cmin的基于模拟的算法并在第3.3节中引入不同的基于模拟算法以确保竞争比率至少为12即使是小cmin。我们最后在第3.4节中提出了两种简单的混合算法可以获得两种竞争比率中的最佳。 3.1我们方法的高级草图 设{y*Stzt}是期望LP[{Ft}t t1]的最优分配。由于∅∈S在不丧失一般性的情况下我们只能考虑最优分配其中 本文中所有基于仿真的在线算法都遵循四个步骤
-在时间t0开始之前 **i预处理**通过调用假设3中描述的离线预言机计算预期LP[Ftt t1]的最优分配yStzt。此外计算算法偶尔需要的任何其他离线参数。 -在每个时间t1、2、。T **ii模拟**当在时间T实现消费者类型zt时外部程序建议通过从S上的分布{ySTzt}S∈S中采样S∈进行分类。 **iii丢弃**对于每个产品i∈SÜ一个单独的内部丢弃程序决定是否将该产品从最终分类中移除考虑到时间t之前的历史和实现的类型zt。如果手头没有可用的产品i则会自动丢弃以保证库存的可行性。否则产品i的内部程序决定是否丢弃。设S⊆S⊂是未放弃产品的集合。 **iv后处理**给定zt、S和S在S的所有子集上选择概率分布FztSS。然后选择一个产品组合S~~Fzt、S、S并提供给消费者。
在上述四步布局中步骤ii是预期LP[{Ft}T T1]的最优解的无损失随机舍入然而最终的分类只保证了预期中每种产品的库存可行性。步骤iii和步骤iv的作用是确定这种可行的期望分类的随机化子集不仅保证每个样本路径中的库存可行性而且还保证由于丢弃产品而造成的预期损失很小。 3.2大型初始库存接近竞争比率1−εcmin* 本小节算法背后的主要思想是在每个时间t的步骤iii中以概率γOp logcmin/cmin随机丢弃每个产品。直观地说这种丢弃尝试为每个时间t不违反任何库存约束留下足够的概率如果丢弃一个产品不会改变另一个分类产品的选择概率则每个产品i在每个时间t的预期不可用单元数为大多数1−γci–由于步骤ii中采样集预期的可行性。现在考虑产品i的租金指标随机变量即表明该产品是否在每次出租的随机变量。如果这些随机变量在时间上是相互独立的那么我们可以使用独立随机变量之和的简单集中边界来证明我们的主张。 上述方法存在两个主要问题I在弱可替代性假设1下丢弃产品I会微弱地增加另一个分类产品j的选择概率如果我们仅模拟期望的LP最优解并以概率γ独立地丢弃每个产品则这反过来增加了该产品在时间t的不可用单元的预期数量。 二 由于资源可重复使用且库存有限产品i在时间τt的租金指标随机变量与同一产品在时间t的租金指数随机变量相关事实上当在时间t实现的租赁持续时间dτ不小于t−τ时第一个指标迫使第二个指标为零产品的最后一个单位在时间τ租赁并且在[τ1t]期间没有产品的单位返回。 我们通过改变算法来解决第3.2.1节中的第一个问题并通过修改分析来解决第3.2.2节中的第二个问题。 3.2.1.子分类抽样 为了解决第一个问题我们提出了子分类抽样程序——步骤iv中使用的后处理程序。该程序确保在步骤ii中未丢弃的产品被到达的消费者以与预期LP基准的最优解中完全相同的概率出租。更正式地说子分类抽样在每个时间t在S的子集上诱导分布FztSS因此 2 目前尚不清楚这种分布Fzt、S、S是否存在但仅能在多项式时间内采样乘积n的多项式然而对于满足弱可替代性假设1和向下封闭可行性假设2的任何一般选择模型我们表明存在这样的分布FztûSS并且我们引入了在多项式时间内递归地从Fzt中采样集合的过程1。7 注释7值得注意的是Goyal等人2020a独立并同时发现了一种类似于我们针对具有对抗性到达和可重用资源的设置的子分类采样的想法。 命题3。对于任何弱可替代且向下封闭的可行选择模型任何分类S∈S以及任何目标概率{pi}i∈S使得所有i∈S的pi≤⑪Si过程1输出满足iS8838S的随机分类Sii对于所有i∈SES hSiipi。 此外它在时间上运行Polyn 算法1 备注2。为了保证在步骤iv中给定任何zt⑪SS的方程2我们通过设置← ⑪ztS← S和pi← 对于所有i∈S´。请注意对于所有i∈Spi⑪zt⑪Si≤ύzt。 命题3的证明。在不丧失一般性的情况下我们假设σ是恒等置换即对于i∈[m]σii。为了显示多项式运行时间观察a每个递归中的运行时间是Polyn和b此递归算法的迭代次数最多为n因为开始时|S|≤n并且作为下一递归调用的输入的S′的大小在每次迭代时缩小1即|S′|≤|S|−1。 建筑持有的财产i。我们通过对m|S|的归纳来展示性质ii即分类S的大小。在这个归纳中我们使用了另一个简单的性质iii即对所有i∈S而言对所有iiPmjiqjpi这通过构造立即成立。 基本情况m1。在这种情况下程序1随机输出∅或S。根据属性iii归纳陈述成立。 感应步长m1。固定任意乘积i∈S。请注意通过构造ESh⑪Si|j*ii0并且ESh⇔Si| j*m iSi。对于任何实现值j*i。m−1及其对应的S′{1…j*}我们可以使用分类S′的归纳假设对于每个i∈S′概率p′iSi。这是真的因为|S′|≤m−1并且对于每个i∈S′作为选择模型的Si≤⑪S′i是弱替代。通过调用归纳法假设当我们在下一个递归调用中使用S′时对于所有ji。m−1。因此调用属性iii 其完成感应步骤并完成验证。 3.2.2 算法与分析 现在我们提出了第一个基于仿真的算法算法2及其竞争比率保证定理1。 算法2 定理1。通过设置γγ*cmin算法2与贝叶斯预期LP基准预期LP的竞争比率[FtT T1]至少为1-ε*cmn1−O p logcmincmin/cmin。更重要的是它在时间上运行PolynTP T∈[T]|Zt|给定oracle对分类优化离线算法的访问权限假设3。 为了解决本节前面提到的第二个问题我们在对算法2的分析中使用了一个谨慎的耦合论证该论证将我们算法的租金指标随机变量与另一个假设算法相耦合。该假设算法忽略了所有产品的库存约束仅模拟了预期LP的最优解以概率γ丢弃每个产品。该算法生成租金指标随机变量的独立序列允许我们使用简单的集中边界。重要的是这种耦合技巧只有在方程2中的子分类抽样程序的保证下才有可能实现这将在稍后的证明中明确。 在证明定理1之前我们回顾了证明中使用的Chernoff浓度边界的乘法形式Chernoff等人1952。 引理1乘性Chernoff界。假设X1X2。Xt是取01中值的独立随机变量。X表示它们的和µE[X]表示和的期望值。那么对于任何δ0 定理1的证明。命题2和命题3很容易证明运行时间。为了证明竞争比我们首先声称对于任何时间段t和产品i存在产品i的可用单位的概率至少为1−exp−γ2 2 c−min定义了以下指标随机变量及其相应事件γ。为了证明这一点Iit在时间t分配产品i的单位的事件I1It产品I在产品组合Sût中的事件I2It在算法2的第6行中产品I未从分类S中删除的事件I3It在时间t开始时库存中有单位产品I可用的事件I4It产品I在St分类中并由消费者t选择的事件Iiτt产品i在时间τ的租赁持续时间至少为t−τ的事件。 注意根据定义IitI1It·I2It·I3I。现在我们的索赔相当于 3 对于任何时间t和乘积i。为了显示不等式3一个问题是{Iit}在t上不是独立的。为了解决这个问题考虑一个假设场景其中我们在没有库存约束的情况下运行算法2并定义随机变量n zt†SÜt†、i†iti1it†i2it†i3iτ的方式与在具有库存约束的算法2的正常运行中完全相同。注意根据定义ii3it†确定等于1iiI†ItI1It†·I2It†·I3It†·Ⅰ4ItI1 It†·Ⅱ2It†·Ⅲ4It:†和iii{I†Iτ·I†Iτt}τ在τ上相互独立。 我们现在使用这个假设场景和算法2的正常运行之间的耦合其中Pτt I†Iτ·I†Iτt≥PτtIiτ·Iitt用于所有It。显然我们可以定义耦合使得zt†← 中兴通讯†← SÜt因此I1It†I1 ItI2It†← I2It和I†Iτt← Ii、τ、t。 此外请注意 其中第一等式因命题3中的子分类抽样的保证而成立第二等式因上述耦合而成立。此外当I3It0时第三等式自动成立而当I2It1时由于命题3中的子分类抽样的保证以及I1ItI3t†的事实第三个等式自动成立。同样由于上述耦合我们得出结论 因此我们可以进一步耦合随机变量I4It†·I3It← I4It·I3It。因此I4It†·I3It†≥I4It†.·I2ItI4。因此足以证明 为了显示上述界限我们首先将期望值E I†Iτ·I†Iτt重写如下 其中我们使用命题3中的E h I4It†|I1It†I2It†I⑪zt†Sût†I·I11†It·I2It†这一事实E h I2It†| I1It†I1−γ随机变量I†Iτ和I†Iτt独立于zτ。因此 通过对独立随机变量序列i†iτ·i†iτt t−1τ1应用Chernoff界引理1的乘法形式我们完成了对我们主张的证明即3中的尾界 图2 现在固定任意时间t和乘积i。考虑乘积i在时间段t对算法2的收益的预期贡献。根据定义它等于 其中第三个等式由命题3成立最后一个不等式成立因为I3It与ri zt、I1It、I2I、t和SÜt相互独立并且通过我们在3中的尾部约束我们有 因此对于任何γ∈[01]算法2至少1−γ1−exp−γ2 cmin 2–γ-与贝叶斯预期LP基准相比具有竞争力。最后设置γγ*cmin完成验证。□ 备注3。我们在本节中的分析主要集中于cmin较大的渐近状态然而通过使用方程1对ε*cmin进行数值计算我们仍然可以绘制算法2的竞争比1−ε*cm in。参见图2中的黑色实心曲线。 3.3小型初始库存达到竞争比率1/2 在本小节中我们提出了第二个基于仿真的算法。该算法与算法2的主要区别在于丢弃步骤如果手头没有可用的产品i单位则自动丢弃以保证库存可行性否则只有当ri zt≥P zt it时才在最终分类中选择其中P zt it是由算法计算的非自适应阈值前面稍后将讨论。这一丢弃程序的目的是确保只有具有足够高租赁费的可用产品被分类。 从技术上讲对于每种产品人们可以考虑一个单独的DP以最佳地做出分类决策。考虑到步骤ii的随机建议召回第3.1节该DP将在有限的时间范围内使产品i的分类单位的单位收入最大化[1:T]。缺点是需要一个高维状态变量来跟踪现有产品库存以及正在使用的产品单位的库存并将在不同时间返回库存。我们算法的一个主要组成部分是用一个与库存无关的简单DP来代替这个高维DP并在Bellman方程中使用实际库存的ci的乐观上界来更新产品的最优单位收入 3.3.1 与补货配合的单位收入动态规划 在本小节的其余部分中对于每个S、t和zt设XS、t、zt≜yS、t、zt Ftzt。假设在每个时间t实现一个新的独立消费者类型ztFt。设SûXStzt表示在步骤ii模拟步骤中采样的随机化子集。固定产品i∈[n]初始库存为ci单位。现在考虑一个假设情景即一个外生过程每次都会补充库存以确保我们手头始终有ci个产品单元无论当前有多少个单元处于租赁状态。在这个新问题中目标是设计一个在线策略一旦在步骤ii中建议就丢弃或接受可重复使用的产品单元以便最大化租赁该产品的单位收入。我们可以使用一个简单的动态规划来表述这个问题其中Vit是在时间间隔[t:t]内产品i的最佳单位收益。与用于解决最优丢弃的原始高维DP相比该DP是乐观的因为它“想象”了每一个周期都会补充库存中的不足。 按照惯例设ViT10。为了使用后向归纳法在时间t编写乐观DP的贝尔曼更新方程假设实现了类型zt并且SÜS这发生在p.XStzt。 如果最优策略决定放弃产品i则单位收益将为Vit1。如果最优策略决定不丢弃i那么在概率为1−⑪ztSi的情况下单位收益仍将为Vit1。8 注释8在这个假设场景中我们假设消费者选择产品i的概率等于⑪ztSi而不管是否从S中丢弃了另一个产品i′。 然而在概率为⑪ztSi的情况下消费者租用了其中一个ci单元请记住库存将始终是满的因此产生的总收入为ci−1Vit1即由于在时间t未租用的单元的贡献这些单元将在时间t1转移到库存中加上ri ztVitd在实现租赁时间dG z i t时即由于租赁单位的贡献。 总之我们将使用以下Bellman更新公式 4 注意可以通过重新排列术语来简化上述动态编程的更新规则有趣的是规则将独立于ci和⑪ztSi因为它们抵消了 5 备注4。稍后在EC.1和EC.5节中我们将用一个稍微修改过的DP替换这个简单的DP该DP具有库存依赖状态但在租赁时间无限时仍然是低维的。 这使我们能够获得几乎这种特殊情况下的最佳竞争比率。 3.3.2 算法与分析 现在我们提出了第二个基于仿真的算法算法3其竞争比率保证定理2。9 注释9定理2中的竞争比率是最优的即使租赁时间是无限的。考虑以下示例有一个具有单个单元的不可重用产品。有两个时间段T2。消费者1具有一种确定性类型即以1美元的价格确定购买该商品。在概率为ε的情况下消费者2的类型决定以1/ε的费用购买该商品。否则即概率为1-ε消费者2的类型是什么都不买的。 在本例中贝叶斯预期LP基准以及透视策略的预期收益为2-ε而任何在线策略的预期收入最多为1。 算法3 定理2。算法3与离线贝叶斯预期LP基准即预期LP[{Ft}T T1]的竞争比至少为1/2。此外它在时间上运行PolynTP T∈[T]|Zt|给定oracle对分类优化离线算法的访问权限假设3。 定理2的证明草图。命题2证明了运行时间第3.3.1节中的简单DP可以在多项式时间内求解。竞争比率的分析可以在产品之间解耦。对于每个固定产品i我们分两个部分进行分析每个部分如下所示参见第EC.4节中的完整细节•第i部分–第EC.4.1节我们首先将算法3与第3.3.1节中描述的简单乐观动态规划进行比较并显示出算法3由于产品i的租金而产生的总预期收入至少为ciVi1。我们使用归纳法证明了这一说法并且事实上显示采样分类SÜt的子集仅能增加遵循乐观DP阈值的丢弃策略的收益如在算法中。 •第ii部分–第EC.4.2节然后我们将这个简单的动态规划与预期LP基准进行比较并表明对于每个产品iciVi1至少是产品i对预期LP的最佳目标值的贡献的1/2[FtT T1]第ii部分。为了证明这一部分我们使用了第3.3.1节中的乐观DP与描述乐观DP竞争比率的相关因素之间的联系。这种联系导致我们应用对偶论证以找到ciVi1的比率和乘积i对预期LP[{Ft}T T1]的最优目标值的贡献的下限。 3.4 算法2和算法3的混合 两全其美的丢弃 在算法2和算法3中我们都有相互独立运行的丢弃策略每个产品一个。此外两种竞争比率分析在不同产品之间基本上是解耦的因为我们分别分析了每个产品的这些丢弃策略的收益表现。此外在这两种分析中我们将每个产品i的预期收入与该产品在预期LP中的贡献进行比较。 考虑到我们两种算法的所有上述设计和分析方面我们可以提出一种混合算法在该算法中我们基于每个产品i的初始库存ci来决定丢弃策略的选择。一旦我们完成了这些选择我们就在最终混合算法的丢弃步骤中为不同的产品并行和单独运行可能不同丢弃算法。为了实现小型和大型库存制度的最佳收益绩效保证我们在一开始就将这组产品划分为初始库存较大的产品和初始库存较小的产品稍后将正式定义。 给定此分区如果ci较大我们分配一个“随机丢弃”策略如算法2中所述以在时间t∈[t]上做出产品i的丢弃决策如果ci较小我们使用“具有单位收入阈值的丢弃”如算法3中所述。为了区分大ci和小ci我们首先通过使用其Bellman更新方程如方程4所述来解决第3.3节中每个产品i∈[n]的乐观DP丢弃策略的动态规划。然后我们使用产品i的乐观DP的值函数Vi1将该产品标记为大库存或小库存。特别地将Ri定义为产品i的乐观DP的预期收益与该产品对预期LP目标的贡献之间的比率即。 注意定理2中的Ri∈[0.51]。还应注意εc在c中是连续单调递增的ε*01且ε*∞0-关于ε*·的定义请参见方程1。接下来我们将比率Ri与1-ε*ci进行比较。事实上如果Riε*ci1我们将随机丢弃的竞争比率排除在外使其不小于乐观DP的竞争比率因此我们将该产品标记为“大库存”。否则我们期望乐观的DP在竞争比方面击败随机丢弃因此我们将产品标记为“小投资”。最后我们执行子分类抽样作为后处理步骤以纠正未丢弃产品的选择概率可能由于替代性较弱而增加其他产品要么被丢弃要么甚至没有在分类中被选择因为它们最初不可用。我们用SimHybridi表示得到的算法。 定理3。SimHybridi与离线贝叶斯预期LP基准的竞争比即预期LP[{Ft}T T1]至少为1−min 蒙特卡洛模拟有帮助 原则上给定类型分布序列FtT T1可以模拟算法2和算法3并使用蒙特卡洛模拟来估计它们的预期未来收入从任何时间T∈[T]开始给定直到时间T的任何历史。现在一个简单的混合算法可以切换到具有更高预期收入的算法并在给定当前租赁产品历史的下一个时间步骤中运行该算法。通过在给定到目前为止的历史的每个时间t重复应用该方法一种称为条件期望方法的技术我们最终得到了一种替代的混合算法该算法本质上是在两项政策中每次都要成为领导者政策这意味着其每次的预期未来收入至少是两项政策的预期未来收益可以使用归纳法证明。因此该混合算法明显地获得了1−min的两个世界的最佳竞争比 备注5。我们想强调的是虽然SimHybridi和SimHyattii都达到了前面提到的理论上的两全其美的竞争比率正如我们在第4节的数值模拟中看到的那样它们在我们问题的实际场景中都优于其他现有策略但它们在计算要求方面有所不同。事实上SimHybridi可以很容易地为每个产品i的丢弃策略的选择做出预先决定与算法2和算法3相比几乎没有额外的计算然而SimHybridii需要通过从未来类型中进行采样来多次运行蒙特卡洛模拟取决于切换频率这使得它在实际中不那么吸引人。
4 数值实验
实验设置。在我们的测试问题中我们有六个由{123456}索引的产品。每个产品的初始库存ci30。我们考虑从自己的“考虑集”中选择的消费者Howard和Sheth 1969Aouad等人2020。考虑到消费者的考虑集我们假设她基于多项LogitMNL选择模型从该集中选择产品。更具体地说我们有六类消费者。类型j∈{123456}的消费者考虑产品[1:j]。给定分类集S她选择产品i∈S其概率为⑪jSiαj i/α0 jP l∈Sαj l。对于类型为j的消费者αj i0表示ij即她不会选择超出其考虑范围的产品。每个非零的αj i都是从区间[0.91.1]随机独立且均匀地绘制的。为了给消费者选择外部选项的可能性我们将α0 j设置为α0 j/α0 jP l∈[1:j]αj l0.1。注意类型1的消费者是最挑剔的思想单一而类型6的消费者是最少挑剔的。对于类型为j的消费者产品i的租赁费r j i是从区间[10·ηjκ25·ηjκ]中随机抽取的其中ηj、κ≜12κ·6−j 5且κ≥0是在我们的模拟案例中变化的参数将在后面详细说明。在为j类消费者生成租赁费rjr1j…r6j后我们重新排序使r1j≥r2j≥…≥r6 j中。 我们考虑了长度T300的离散时间销售/租赁期限以及以与Rusmevichientong等人2020类似的方式针对不同类型到达的非平稳模型。粗略地说为了得到最坏的类型分布顺序我们打算有一个到货订单在那里挑剔的消费者会在销售期晚些时候到达。通过这种方式政策需要为这些消费者谨慎地保留足够的库存如果没有租赁或者考虑产品的有限租赁期限并谨慎地管理以便在挑剔的消费者到达时如果有租赁有足够的物品返回库存。为了捕捉这种到达方式我们将销售范围划分为长度相等的块τT/6。设τj6−jτ1对于j12。6. 在每个时间tj型消费者以与e−0.001κ| t−τj|成比例的概率到达即。 6 注意κ0对应于来自均匀分布的类型的i.i.d.到达。随着κ的增加到达变得更加异质以类型的降序向确定性到达收敛。 我们考虑两类场景第一类场景没有租金见图3第二类场景有租金见图4。对于每个类别我们考虑与κ∈{0123}相对应的四个测试场景。 在第一种情况下我们为每种产品i设置初始库存ci30。类型j的消费者的产品i的租赁持续时间被设置为随机变量T/10Xj 其中Xj是几何分布的其平均值从模拟开始时的间隔[20·η7−jκ20·η。 为了衡量每个场景中不同策略的预期收益我们考虑通过进行50次蒙特卡洛模拟迭代在输入的独立样本路径包括类型实现、消费者选择和租赁持续时间上运行目标策略。然后我们记录所有运行/样本路径的产生收入并使用“盒和须”图来证明这些数量的中值收入和由此产生的置信区间图3和图4。 此外我们计算所有运行/样本路径的平均收入作为每个策略的预期收入的估计表1和表2。 政策。在我们的数值实验中我们比较了本文或之前工作中提出的八种不同策略/基准的预期收益1。库存平衡IBGolrezaei等人2014通过跟踪可重复使用产品的库存水平对库存平衡算法进行了调整。对于我们的实验我们考虑使用指数惩罚函数Ψxe1−x−e1−e的变体。 2.近视贪婪策略GR给定每个时间段的可用产品GR此时提供近视最佳分类。当Ψx✶x0。 3.贪婪与价值的线性近似GR APXLinValue该政策是Rusmevichientong等人2020提出的近似DP政策本质上是一种贪婪的近视政策与最优收益函数的线性近似有关。更多详情请参见Rusmevichientong等人2020的第3节。 4.推出政策推出该政策通过对Rusmevichientong等人2020第4节中提出的静态政策应用推出10获得。 注释10在这种情况下静态策略的推出是通过首先使用bakward归纳法计算静态策略的收益-收益函数来计算的然后在假设未来收益等于静态策略的计算收益-收益值的情况下贪婪地选择每次的最佳分类。 5.分解Deco该策略是Liu和van Ryzin2008提出的另一种近似DP策略它首先分解产品中的原始DP然后通过求解每个产品的单独DP来构建价值函数近似值。该策略在实践中被广泛使用但没有理论性能保证。 6.具有混合丢弃规则的基于仿真的策略Simhybridi该策略是第3.4节中讨论的第一类基于仿真的混合策略。具体而言对于每种产品它比较了不同丢弃策略的近似保证即算法2中的随机丢弃和算法3中的每单位收入阈值以及算法4中无租金场景的库存相关收入阈值。然后分别为每个产品选择具有更高近似保证的丢弃策略 7.基于模拟的策略通过蒙特卡洛模拟进行混合Simhybridii该策略是第3.4节中讨论的第二类基于模拟的混合策略。具体而言在每10个周期之后它通过进行20次蒙特卡洛模拟迭代来估计算法2和算法3以及无租金场景的算法4的预期未来收入并转向具有更高估计未来收入的政策。 8.贝叶斯预期LP该基准是第2节中定义的贝叶斯LP基准预期LP[{Ft}T T1]。它提供了任何可行在线政策的预期收入上限当预期被接管类型、消费者选择和租赁期限的随机性以及政策的内部随机性时。 表1表2 后果为了总结我们在本节中运行的模拟结果我们分别考虑了上面提到的两个类别1。无租金在这种情况下从表1和图3可以明显看出SimHybridi和SimHyattii在所有κ方面的性能明显优于其他产品。具体来说通过对场景κ∈{0123}进行平均将其他策略与我们的混合策略进行比较 SimHybridii的平均性能比GR分别为Deco、GRAPXInValue、Rollout、IB、SimHybridi高33.2%分别为26.0%、30.8%、28.4%、15.3%、0.3%。值得注意的是SimHybridi和SimHybridii之间的差距很小。 注释11值得一提的一点是Rusmevichientong等人2020报告了在非常相似的模拟设置中与IB相比推出的性能更好。虽然这在表面上看起来是矛盾的但我们验证了这种差异背后的原因是他们每100个时间段重新计算Rollout使用的近似值这提高了其性能。为了进行公平比较我们没有重新计算任何参数。 随机和有限租金在这种情况下从表2和图4可以清楚地看出SimHybridi和SimHyattii在所有κ方面的表现明显优于其他政策。 具体而言SimHybridii的平均性能比GR分别为Deco、GRAPXLinValue、Rollout、IB、SimHybridi高24.8%分别为21.8%、42.9%、34.8%、8.3%、5.5%。 图4当存在具有随机持续时间的依赖于类型的租金时不同政策在预期收入方面的盒和胡须比较。结果基于蒙特卡洛模拟的50次迭代。
5 结论
我们研究了在贝叶斯环境中为可重用资源的在线分类设计近乎最优的算法。我们提出了一个基于四个模块化步骤的算法框架i解决预期的LPii模拟解决方案iii为每种产品运行单独的丢弃程序以保持逐点库存的可行性同时仅损失每种产品收入的可忽略部分以及iv执行后处理步骤以调整未丢弃项目的选择概率。使用该框架我们设计了一个在一般租赁持续时间分布下为1−min1 2O p logcmin/cmin的算法以及在无限租赁持续时间下具有竞争比1−1/pcmin3的改进的近最优算法。不仅如此我们的算法在理论上优于文献中的现有算法我们通过数值模拟进一步验证了它们的收益性能优势。 作为未来的路线图研究现实世界分类问题中除可重用资源之外的其他实际方面可以建模以及数学编程技术可以在多大程度上用于设计有竞争力的算法是很有意思的。在技术方面我们工作中最直接的公开问题是找到一般租赁期限分配情况下的最佳竞争比率。特别是我们可以在我们的竞争比率中去除对数因子获得1−O1/√cmin竞争算法类似于不可重复使用情况下的最佳已知竞争比率吗作为一个不同但更具雄心的未来方向进一步研究类似于贝叶斯在线分类的随机在线优化类将是有趣的以便发现计算的计算难度或近似最佳在线策略即DP策略。这里一个有趣的发现是通过多项式时间策略获得针对最佳在线基准与预期LP基准的改进近似值a la Anari等人2019或证明其不可能
EC.1讨论和辅助结果
EC.1.1。静态与动态替代和子分类抽样。 在本节中我们讨论了文献中研究的静态替代和动态替代的子分类抽样与分类优化之间的联系参见。 Ma等人2018。我们首先介绍了静态替代和动态替代的定义然后讨论了它们与离线单镜头分类问题中的子分类抽样的联系最后我们将讨论扩展到本文所考虑的在线多时段分类问题。 在我们的模型中平台只能形成可用产品的组合。另一种模式假设是无论产品的可用性如何平台都可以形成产品组合。 在这个替代模型中我们区分了消费者如何根据显示的产品种类和可用性做出决定的两种设置。 •静态替代给定所有产品的分类S和可用性状态选择模型为的消费者选择项目i的概率为Si只有当所选产品i可用时销售才是最终的。 •动态替代给定产品类别S和所有产品的可用性状态具有选择模型的消费者选择项目i其概率为Si其中产品类别S包括S中的所有可用产品。根据定义消费者从不选择不可用产品。 值得注意的是在离线单镜头分类问题中子分类抽样在静态替代和动态替代之间建立了以下联系。 提案EC.1。对于任何弱可替代和向下封闭的可行选择模型⑪、任何分类S∈S和任何可能的产品可用性存在一个随机分类S使得对于每个产品i∈[n]产品i在静态替代中被分配在类别S下的概率等于产品i在动态替代中被配置在类别S下的预期概率在S的随机性上。 证据通过设置⑪调用命题3← ⑪秒← S和pi← 对于所有i∈SSi完成证明。□ 在在线多周期分类问题中我们基于模拟的算法首先基于贝叶斯期望LP期望LP的最优分配对分类SÜt进行采样[Ftt t1]然后通过移除不可用的产品以及丢弃程序建议丢弃的产品来构建分类S´t。我们将静态替换的定义调整如下。 •带取消的静态替代给定产品组合S选择模型为的消费者选择产品i的概率为Si。观察消费者的实际选择后平台可以立即收回该产品i而无需为丢弃或因不可用而支付任何费用。 在带抵消的静态替换下我们可以简化基于模拟的算法算法2和算法3并通过如下修改后处理步骤来保持相同的竞争比率保证定理1和定理2向消费者t提供分类SÜt如果i̸∈SÜt则收回消费者t选择的产品i。上述修改算法3的竞争比率保证遵循与之前完全相同的论点。为了了解为什么上述修改的算法2保持了竞争比请注意与定理1中算法2的论点类似的论点仍然成立。特别地我们可以考虑一个假设场景其中我们在没有库存约束的情况下运行修改后的算法2并且正常运行修改后算法2有趣的是在带抵消的静态替换下这一次两种场景之间的耦合变得微不足道然后假设场景的集中度论证结束了论证。 另一方面具有动态替代的在线多周期分类问题本质上是正文中考虑的确切问题。在这个意义上定理1的证明中的子分类抽样和耦合论证可以被解释为从具有动态替换的在线分类问题到具有静态替换具有取消的在线分类
EC.1.2.提高了不可重复使用案例的竞争比率。 作为一个副作用主要是为了我们的数值模拟我们在第EC.5节中考虑了不可重用资源的贝叶斯在线分类的特殊情况Rusmevichientong等人2020对此进行了研究。 我们遵循基于模拟的方法然后类似于第3.3.1节我们使用动态规划来捕获该产品的最佳丢弃策略的预期收益当产品从基于仿真的外部算法接收到概率建议以放入分类时。12(注释12此动态规划是Alaei等人2012中先知不等式匹配动态规划的推广这一次的主要区别在于我们实际上可以计算并运行精确的最佳丢弃DP。)为此固定乘积i∈[n]。注意在无限租赁期的情况下当前库存水平起着状态的作用这是一个单调递减的数量因为产品的单位永远不会返回库存因此DP具有多项式大小的状态空间并且原则上可以有效地计算即在多项式时间内。 事实证明解决这个DP与Alaei2014中介绍和研究的“魔术师问题”密切相关这本身就是一个在线竞争解决方案的特例简单均匀拟阵环境Feldman等人2016。通过利用本文中介绍的技术并将其扩展到贝叶斯在线分类优化问题我们表明遵循最优DP的丢弃算法损失的LP预期收入不超过1√cmin3这与魔术师问题中的近似因子相同。 具体而言假设E I It表示当I是时间t的剩余库存时产品I在[tt]期间从最优丢弃策略中获得的预期收入。类似于第3.3.1节中关于单位收入阈值的讨论假设在时间t对分类SûXStzt进行采样。 如果DP丢弃策略丢弃来自抽样分类S的产品i则预期收益变为E i it1否则消费者选择产品i的概率为⑪zt⑪Si13(注释13与第3.3.1节相似这里我们考虑一个假设场景其中消费者选择产品i等于⑪zt⑪Si的概率而不管是否从S中丢弃了另一个产品i′。)预期收益为E i−1 it1ri zt。在剩余概率下产品i未被选择预期收益为E i it1。因此我们可以使用动态编程即反向诱导使用以下Bellman方程计算E I It (EC.1) 重新排列术语后很容易观察到DP决策是由依赖于库存的收入阈值规则做出的这独立于{⑪ztSi}因为这些术语抵消了 () 现在我们已经准备好用一个新的丢弃规则来呈现我们完善的基于模拟的策略。该规则使用上述依赖于库存的阈值其中这些阈值是预先计算的但它们取决于产品、时间和产品的当前剩余库存水平。详见算法4。 定理EC.1。设cminmini∈[n]ci为最小库存。算法4与离线贝叶斯预期LP基准即预期LP[{Ft}T T1]的竞争比至少为1−1√cmin3。此外它在时间上运行PolynTP T∈[T]|Zt|给定oracle访问离线算法进行分类优化假设3。 该证明遵循与定理2的证明类似的结构。详见第EC.5节
EC2.最佳离线的无限竞争力
在本节中我们构建了一个简单的例子表明贝叶斯期望LP期望LP[{Ft}T T1]至多是最优离线的O1/T近似。结合命题1这意味着任何在线算法都不能实现与最优离线相比的T无关有界竞争比。 算法4 定理EC2。贝叶斯期望LP期望LP[{Ft}T T1]至多是最佳离线的O1/T近似。 推论EC.1。没有一种在线算法能够实现与最优离线相比的不依赖于T的有界竞争比。 定理EC.2的证明。考虑以下实例其中有一种产品和一种消费者类型。对于该产品其初始库存为1奖励为1。一旦分配了该产品实现的租赁期限为一即在下一时间段内可用概率为1/2否则为无限。在每个时间段t∈[t]具有这种单一消费者类型的消费者以概率1到达平台。消费者选择该产品如果有的概率为1。 首先我们声称最佳离线的预期收入至少为T/2。请注意最佳离线观察产品在分类前每个时间段的租赁持续时间实现情况因此它可以在该时间段内实现租赁持续时间时对产品进行分类周期是一。由于此类时间段的预期数量为T/2因此最佳离线的预期收入至少为T/2。 接下来我们考虑贝叶斯期望LP期望LP[{Ft}T T1]及其对偶程序 考虑双重方案中目标值为2的以下可行双重方案 调用上述原始对偶线性程序之间的弱对偶完成证明
EC.3第2节提案1中省略的证据。
对于任何类型的分布FtT T1千里眼最佳在线基准的预期总收入由预期LP〔FtT1〕上限。 证据设IStz∈01是透视最佳在线基准在给定类型序列zztt1的时间t提供集合S的指示符。由于透视最佳在线基准对于租赁持续时间ddtT1的任何样本路径都是可行的因此对于所有i∈[n]T∈[T]我们有 现在请注意随机变量dτ独立于随机变量isτz因为透视最佳在线基准在时间τ对集合进行分类时无法看到dτ。因此设置yStztE IStzzt导致在对应的线性程序中对任何类型分布序列Ftt t1的期望LP[{Ft}t t1]的可行赋值要看到这一点首先考虑到租赁期限上的上述不平等的LHS然后考虑到类型是独立的考虑到z。此外此任务下预期LP[{Ft}T T1]的目标值将等于千里眼最佳在线基准的预期收益该基准完成了证明。□ 提案2。给定离线分类的算法假设3可以在时间PolyntP t∈[t]|Zt|中有效地计算期望LP[{Ft}t t1]的最优分配{yStz{t}。此外yStzt}不超过PolyntP t∈[t]|zt|个非零条目。 在证明上述命题之前我们首先陈述了一个关于椭球算法的技术引理并简要说明了其证明参见Gr¨otschel等人1981年的详细证明。 引理EC.1。假设一个原始线性规划是有界且可行的。此外假设其对偶具有运行时间最多为τ的分离预言。然后primal接受一个最优解该最优解具有Polyτm非零项并且可以在Polyσm时间内计算其中m是对偶变量的数量原始约束。 引理EC.1的证明草图。因为原始LP是可行且有界的所以对偶也是可行且有边界的。现在考虑使用分离预言运行椭球算法来解决对偶问题。 椭球可以在Polyτm时间内解对偶。现在通过观察椭球体的运行并仅考虑椭球体返回为违反的对偶约束我们可以在对偶中找到Polyτm许多约束使得如果我们丢弃剩余的约束对偶值不会改变。 注意对偶中的约束对应于原始中的变量。因此我们可以丢弃原始变量中的所有变量除了与分离预言要求我们保留的对偶约束相对应的变量LP值不变。现在我们在原始中有一个紧凑的LP我们可以再次求解以获得具有Polyτm非零项和时间Polytm的简洁原始解。□ 命题2的证明。给定引理EC.1我们已经准备好证明离线预言机可以有效地解决预期的LP。预期的LP[{Ft}T T1]具有指数级的变量和nTT约束。因此它的对偶只有nTT个变量和指数多个约束。 这里是对偶LP具有对偶变量θi、t和λt 现在固定t∈[t]zt∈zt并考虑对应于t和zt的对偶约束组。为了获得这组约束的分离预言给定λtzt和{θiτ}需要找到一个集合Sû∈arg max S∈S X n i1ûRiěztSi其中 那么如果λtzt≥X n i1⑪Ri⑪zt⑪Si则满足这些约束如果不满足则对应于tztS的约束是分离超平面。注意由于S的向下接近性即假设2以及⑪ztSi的弱可替代性即假定1我们可以丢弃其中Ri0的产品因此在不丧失一般性的情况下假设Ri≥0。因此多亏了假设3只需调用一次预言就可以找到这样的子集Sû。通过对所有可能的t和zt进行多项式时间搜索对偶将得到一个运行时间为PolyntP t∈[t|zt|的分离预言。调用引理EC.1完成证明。□
EC.4.第3.3节小库存省略的技术细节
在本节中我们对定理2中所述的算法3的竞争比进行了详细分析。如定理2的证明草图所述分析由两个主要部分组成。我们首先将算法3与第3.3.1节中描述的简单动态规划进行比较并显示由于产品i的租金算法3的总预期收入至少为ciVi1第i部分附录EC.4.1。然后我们将该简单动态规划与预期线性规划基准进行比较1至少是产品i对预期LP[{Ft}T T1]的最优目标值的贡献的1/2第ii部分附录EC.4.2。将这两部分结合起来就完成了定理2的证明。 EC.4.1.证明的第i部分与乐观DP相比 在这一部分中我们使用向量变量JJ1…JT来跟踪固定产品i的库存状态其中JT是在时间t将返回库存的产品i的副本数量。注意在每个时间t可能的状态J具有以下形式 其中P TτT Jtci。现在假设QitJ表示当算法在时间t从初始状态J开始时算法3从时间t到t产生的产品i的单位收入。 14注释14等价地QitJ等于[t:t]中产生的产品i的总收入除以JtJt是开始时间t时产品i的现有单位数。按照惯例设QiT1J0。我们证明了以下更强的引理这也表明产品i产生的总收入不低于ciVi1。Lemma EC.2背后的直觉如下Vit是通过乐观DP计算的该DP“想象”库存的不足在每一个时期都会得到补充预期收益是库存水平的凹函数——即库存水平越高单位预期收益越低。 引理EC2。对于时间t处的每个t∈[t]和每个可能的库存状态JQitJ≥Vit。 证据为了简化证明我们首先假设算法不执行作为后处理步骤的子分类采样因此S ~t与S ~t相同。在这个简化假设下我们首先完成了证明。然后我们将证明中的分类集St替换为St⊆St时证明仍然保持完整这是在算法3的后处理步骤中使用子分类抽样程序时的相关情况。 该证明基于对t的反向归纳。对于归纳的基础Qit1JVit10。 现在假设在[t1:t]和可能状态J中的任何时间引理的陈述成立。我们可以只需为QitJ编写以下更新方程遵循与方程4中动态编程的更新规则完全相同的逻辑但考虑到手头只有Jt产品 EC.2 其中S⊆S是丢弃步骤后算法3中为消费者t提供的分类J′≜0…00JtJt1Jt2…Jt是时间t1的下一个状态如果在时间t没有发生出租如果出租发生在时间t出租持续时间为d其中该状态的随机性来自未来时间[t1td−1]期间的所有类型实现和消费者选择则Jτd是算法3在时间tτ的随机化状态。现在通过将我们的归纳假设应用于等式EC.2和弱替代即对于所有i∈Si而言Si≤⑪´Si我们得到 EC.3 还应注意上述不等式的RHS作为Jt的函数是不增加的这仅仅是因为如果1Jt增加了加性ε0则RHS增加了 因此当Jt≤ci时我们有 现在假设我们在后处理步骤中使用子分类采样步骤1。执行此后处理步骤不会降低算法3中“每单位收入阈值”P zt it丢弃的收入保证。事实上显示S的任何子集例如每次子分类抽样程序的输出S⊆S只能增加遵循乐观DP阈值的保单的单位收入。更准确地说在某个时间t查看上述证明中的归纳步骤。当ri zt≥P zt it时等式EC.3中第一个不等式的右手边只能增加如果我们用S⊆S⊂代替S简单地说因为由于弱替代所以当ri zt≥P zt it时方程EC.3中第一个不等式右手边的系数为非负因此。其余的归纳法类似于简化的案例完成最终的证明。 EC.4.2.第ii部分比较乐观DP与预期LP 为了证明这一部分我们使用了第3.3.1节DP与相关LP之间的联系。 这种联系导致我们应用简单的对偶论证来找到ciVi1的比率和乘积i对期望LP的最佳目标值的贡献的下限[{Ft}T T1]。 注意缩放{ri-zt}不会改变比率。因此在不丧失一般性的情况下我们将乘积i对期望LP[{Ft}T T1]的最优目标值的贡献归一化即。 鉴于上述观察结果和4中的Bellman更新考虑以下给出比率最坏情况值下限的原始线性程序 EC.4 其中我们允许V{Vit}t t1和r{ri-zt}t∈[t]zt∈zt都是变量这是该技术的一个重要特征。我们首先通过切换第一个约束的RHS中的外部求和和最大算子来放松和简化这个程序这只会使RHS变小因此是放松。还应注意 现在通过将新的约束Vit≥max{AB}替换为两个约束Vi、t≥A和Vit≥B我们得到以下最终原始线性规划 Primal-LP1 现在我们用对偶变量{αt}、{βt}和µ编写其对偶程序如下 Dual-LP1 现在我们尝试猜测对偶程序的可行解以获得最优原始目标的期望下界。为此让∀t:αtµci因此第一组约束将自动满足并让所有其他约束都严格。特别地β1ci-α1ci1-µ并且对于所有t∈[2:t] 其中1可以通过改变求和的顺序并重新排列项来获得并且2由于{y*Stzt}在预期LP[{Ft}t t1]中的库存可行性而成立。现在设置µ1/2可以保证双重可行性因为∀t:αt≥0βt≥0。通过应用弱对偶期望的比率至少为µ1/2这完成了证明。
EC.5.无限租赁持续时间特例的省略细节
在本节中我们考虑了租赁时间无限的情况即一旦消费者购买了产品他们就再也不会返回平台。在这种情况下每种产品的库存水平随着时间的推移逐渐降低。这使我们能够使用动态规划在多项式时间内开发依赖于库存的丢弃策略。这些丢弃政策比第3.3.1节中讨论的单位收入阈值政策更为精细并实现了更好的竞争比率即1−1√cmin3这在库存较大时接近最佳。 定理EC.1。设cminmini∈[n]ci为最小库存。算法4与离线贝叶斯预期LP基准即预期LP[{Ft}T T1]的竞争比至少为1−1√cmin3。此外它在时间上运行PolynTP T∈[T]|Zt|给定oracle访问离线算法进行分类优化假设3。 定理EC.1的证明遵循与定理2类似的结构我们首先使用归纳法来证明{EI it}是算法4的未来收益的下限第i部分然后引入线性程序来证明E ci i1至少是乘积i对预期LP的目标值的贡献的1−1/√ci3第ii部分。 定理EC.1的证明。命题2证明了运行时间第3.3.1节中的简单DP可以在多项式时间内求解。竞争性证明分为两部分第一部分。在这里我们显示了对于任何产品i、时间t和库存i算法4中的产品i和当前库存i在时间t的未来预期收入至少为E i it通过时间t从t1到1的归纳。由于我们的边界假设E I It10所以满足基本情况tt1。 现在假设从时间t1到t1诱导假说成立。考虑时间t的算法。以概率XStzt对分类Sû进行采样。让S⊆S⊂是丢弃后在时间t提供给消费者的产品组合。对于库存为i的任何产品i如果E i−1 it1ri ztE i it1则算法将其丢弃。通过在时间t1的诱导假设它保证获得未来预期效用至少最大值{EI it1⑪zt´Siri ztE i−1 it11-⑪zt´SiE i it1}。由于选择模型满足可替代性假设1因此对于所有i∈S∈zt⑪Si≤⑪zt。因此通过与引理EC2的证明类似的计算归纳假设在时间t时成立即e i it下界为产品i的未来预期收入和时间t的库存i。因此算法4从时间1开始的产品i的预期收入至少为e ci i1。 第ii部分。这里我们显示E ci i1至少是产品i对预期LP目标值的贡献的1−√c 1 i3分数[FtT T1]。注意缩放{ri-zt}不会改变比率。 因此在不丧失一般性的情况下我们将乘积i对期望LP[{Ft}T T1]的最优目标值的贡献归一化即。 鉴于上述观察结果和EC.1中的Bellman更新考虑以下给出比率最坏情况值下限的原始线性程序 EC.5 其中变量是{ri zt}和{EI it}。为了证明我们的结果足以证明对于所有可行的库存{XStzt}即P tztS XStzt⑪ztSi≤ci程序EC.5的值至少为1−√c 1 i3。为了看到这一点我们通过切换外部求和和最大算子来放松EC.5中的第一个约束这提供了如下放松的线性程序 我们用双变量αt I、βt I和γ编写其对偶程序如下 通过弱对偶任何可行的对偶解都提供了原始解的下界。 设qt≜P zt∈zt P S∈S XStzt⑪ztSi。根据定义P T T1 qt≤ci。现在假设我们有兴趣生成一个可行的对偶赋值其中对应的所有约束都是紧的即以下程序的解决方案分配EC.6 注意下面的引理EC.3足以完成定理EC.1的证明。 引理EC.3。对于任何非负序列qtT T1使得P T T1 qt≤ci程序EC.6的目标值至少为1−√c 1 i3。 为了显示引理EC.3我们使用了在Alaei2014中开发的技术引理定义EC.1引理EC.4如下所述。 定义EC.1砂/屏障工艺Alaei 2014。考虑一条无限长的胶带在位置0处有一个单位的无限可分割的沙子在位置1处有一道屏障。q1。qT所有qT∈[01]和参数γ∈01作为输入。沙子和障碍物在T轮中逐渐向右移动。在第t轮发生以下情况。 选择磁带上最左侧的砂的γ分数并将该砂的qt分数向右移动一个位置。这可以正式定义如下。设s j t表示t轮开始时位置j处的砂量设yt j∈[01]表示t轮期间从位置j处选择的砂分数。选择yt j使得P i s j tyt jγ并且对于某个整数θt对于任何jθtyt j1对于任何jθtyt j0。因此在第t轮期间一定数量的沙子从每个位置j移动到位置j1。当障碍物位置的沙子总量超过1−γ时障碍物在任何一轮结束时向右移动一个位置。我们将使用λt表示在t轮开始时屏障的位置。 引理EC.4砂/屏障过程Alaei 2014。对于任何γ和任何序列q1。qn在整个砂/障壁过程中第t轮开始时障壁的位置即λt满足 引理EC.3的证明。我们现在通过使用沙子/屏障论点来构造程序EC.6的这种可行的解决方案。设s j t、yt j和λt为定义EC.1的沙/屏障过程中定义的变量参数为tqtt∈[t]γ1−√c1 i3。将不同的库存水平视为砂带上的不同位置但顺序相反。换句话说位置ci−I对应于库存水平I基本上沙子从较高的库存水平移动到较低的库存水平。我们有T轮沙子/屏障过程。在该过程的第t轮对于i∈[ci]在每个位置ci−i处总共有s c t i−i个沙子单位。沙子st ci−I的量分为决定αt I的选定沙子s c t I−I yt ci−I和决定βt I的未选定沙子st ci–I1−yt ci–I。总之我们如下构造对偶解 注意程序EC.6中的所有约束都通过上述双重构造得到满足。根据定义EC.1中对砂/屏障过程的描述如果屏障从未通过位置ci即λT1≤ci则只有胶带的ci位置才会有砂因此该结构定义明确。调用引理EC.4并重新排列术语完成证明。□
