综合规模和价格优化问题

不等式（21）模型中，销售不可能超过库存，在不等式（22）中，我们要求，只有选择价格p，才能以价格p销售，价格p最多等于pric e p的需求。因为目标倾向于更大的销售，在非最优解中，以价格销售的变量将恰好成为该价格下库存和需求的最小值。在平均值水平上，这高估了平均销售额；因此，这只能得到一个近似值。最后，我们通过等式（23）计算货币的收益率。在这个流行阶段，只有独立的价格分配变量被认为是二进制的（24）。在（26）到（28）中，捕获平均库存、销售和收益动态的因变量必须是非负的。目标函数减去处理m批类型的成本l b区和地块类型使用第一、第二、，第i个新的彩票类型（1）来自预期的贴现平均收益率减去预期的折扣成本（2）。这种与ISPO具有确定性的ILP模型——尽管只是一种近似值——包含了许多现实世界的限制和成本因素。因此，标准解算器（cplex，scip）的分支和绑定阶段在我们所有的现实世界中都没有取得任何进展，这并不奇怪。通常的真实规模实例有1500个分支，5个大小，大约2000个批次类型，其中最多5个可以使用，4个价格，在13个周期（通常是几周）的时间范围内进行优化，预期超过3个成功场景（成功率高于/大约/低于平均水平）。

这就产生了一个庞大而复杂的DILP，目前还不能用商业化的货架方法来解决。因此，在下一节中，我们将介绍一个精确的算法（相当快，但对于日常操作来说还不够快）和一个启发式算法（对于日常生产使用来说足够快，并且在所有实际测试中只有极小的最优性g AP）。第3节中给出的ILP公式无法直接求解。我们在本节中给出了一个精确的分枝定界算法。其主要思想是对价格优化阶段的决策进行分析。由于价格优化阶段的变量（见第3节）过于细粒度，我们考虑更广泛的决策。一个自然的想法是将每个时间段内的降价决策浓缩为给定场景e的整个价格轨迹∈ E.我们可以通过插入Pmax对可行的降价策略或价格轨迹进行编码- 1表示标记的符号，如e。G, 进入序列1，kmax- 1（0期价格π是固定的）。下面给出了一个例子1, 2, , 3, 4, 5, 6, 7, , , 8, 9, 10, 11, 12, ,这意味着我们在销售第3期之前降价一次，在销售第8期之前降价两次。第四种可能的降价在批发期结束后延迟。更准确地说，不同销售周期的具体价格如下所示：IBM ILOG CPLEX版本12.1SCIP版本2.1。0综合规模和价格优化问题9销售期0 1 2 3 4 5 6 7 8 9 10 11 12价格ππππππππππππππππππππππππππππππππππ|K |+|P |- 4 | P |- 2.=kmax+pmax- 2pmax- 1.可行的降价策略或价格轨迹，即在我们的示例中= 1820每种情况下的价格轨迹。分支步骤和边界步骤的具体细节见第4节。6.

作为剩余尺寸优化阶段的上界，我们使用定制的组合边界（见第4.2小节，可以有效计算）和线性松弛。从算法上讲，这些下限的高效计算是基于某个子问题的快速解，见第4小节。1.为了消除这些小细节导致的一些并发症，我们也可以假设我们通过直接使用c对应的ILP公式来解决SOP子问题，见第4小节。4.不计算任何更便宜的界限。在第6节中，我们给出了所提出的brand and Bounder算法的计算结果。作为一种启发式，也可以在分支和边界的开头使用，我们在第4小节中介绍了所谓的乒乓启发式。7.结果表明，它在只需要很少计算时间的情况下，就可以获得非常好的解决方案质量。其基本思想是迭代求解尺寸优化和性能优化阶段的分离子问题。然后将一个子问题的临时解作为另一个子问题的输入。为此，我们提出了一种精确但相当简单的精确算法，用于子节4的有奖优化阶段。5.为了提高乒乓球的速度，我们可以使用[11]中关于尺寸优化子问题的SOP的启发式方法，我们在第4.3小节中回顾了这个问题。本节的剩余部分安排如下。首先，我们介绍了解决子部分4中固有子问题的方法。1–4.5.对于第一次阅读，可以跳过这些内容。在4.6小节中，我们介绍了我们的主分支定界算法，在4.7小节中介绍了乒乓球启发式算法。4.1. 工作内容1：以最低成本将供应量调整到总供应量限制。

假设我们想要解决以下相当普遍的二元线性问题：minXv∈ VXa∈常闭触头∈Bψ（v，a，B）·xv，a，bXa∈常闭触头∈Bxv，a，b=1五、∈ V（29）Xv∈ VXa∈常闭触头∈B~n（a，B）·xv，a，B∈ [R，R]（30）xv，a，b∈ {0, 1} 五、∈ 五、 a∈ A、 b∈ B、 （31）式中（1）ψ（a，B）在B中单调增加，（2）ψ（v，a，B）在B.10 M.基斯林，S.库尔兹和J.兰巴瑟。这个问题的连续松弛可以通过贪婪的方法解决：在初始化阶段，我们确定每个v∈ V和每个a∈ A最佳值bv，A∈ B，最小代价ψ（v，a，B）使用二进制搜索。这可以是一个在O|V | | A | log（|B |）台阶。我们用v（a）表示元素a∈ A使ψ（v，A，bv，A）最小化，并通过v（b）相应的值bv，v（A）。用这个我们设置xv，v（a），v（b）=1表示所有的v∈ V.所有其他值均设置为零。如果不等式（30）由纯偶然性满足，那么xv，a，b变量的当前分配将产生全局最优解。否则我们必须调整xv，a，bin以满足资源建设。简而言之，我们只讨论以下情况：∈ VPa∈APb∈B~n（a，B）·xv，a，B>R。另一种情况类似。在这里，我们必须反复地从一些v∈ V.为此，我们引入了相对成本-v、 每个v∈ V和每个备选方案a∈ A.使用（32）βv（A）=max{b∈ B |~n（a，B）<~n（v（a），v（B））}，对于给定的a∈ A、 换一对的相对成本v（a），v（b）到a、 βv（a）由（33）给出-v、 a=ψv、 v（a），v（b）- ψv、 a，βv（a）φv（a），v（b）- φa、 βv（a）每个资源项。如果{b∈ B |~n（a，B）<~n（v（a），v（B））}= 我们将相应的相对成本设置为-v、 a=∞.

B yω（v）∈ A我们用较小的相关费用来表示替代者-1v:=min{-v、 a | a∈ A} =-v、 ω（v）和v我们用V表示元素，其中ω（v），βv（ω（v））实现全球最小的相对成本。作为缩写，我们使用R=Pv∈ Vа（V（a），V（b））和δ=а五、（a） ，v（b）-φω（v）), βv（ω（v）)). 由于目标函数的凸性，我们可以陈述如下：（a）如果-五、= ∞, 那么这个问题就不可行了。（b） 如果R- δ ≥R、 然后在对这一对进行了最佳重演后五、（a） ，v（b）通过ω（v）), βv（ω（v）))新的赋值对应于问题m的最优解，其中不等式（30）被PV取代∈ VPa∈APb∈B~n（a，B）·xv，a，B≤ R- δ.（c） 如果R- δ<R我们利用新旧赋值的适当线性组合，得到了分数变量xv，a，bby的松弛问题的最优解。因此，在经过有限次迭代后，根据初始总体资源消耗a和R之间的差异，我们得到了问题的最优解，最多有两个分数变量xv，a，b。我们注意到，利用abranch和bound方法也可以解决积分问题——我们不在这里详细讨论。4.2. 2：Si-ze优化问题的上界。在算法的其他部分，我们需要一个计算上廉价的dua l，即SOP的上限，具有固定的场景e和价格轨迹t。

我们根据每个规模的每个分支机构的单个供应的完整性来确定我们的第一个上限，从而放松了基于批次的分配所产生的限制。综合规模和价格优化问题11如果我们向规模为s的分支b提供Ib，sitems，那么我们可以计算成本λe，tb，s（Ib，s）：=Pk∈Kexp(-ρk）rek，b，s∈ R≥0直接使用e、t和Ib来评估依赖变量rek、b、s。在多重性m中，供应带有l类型批次的分支b会导致cb、l、m的处理成本。让cb、s（i）≥ 0是可与大小为s的分支机构A的应用与i项目相关联的成本的一部分。λe，tb，swe表示λe，tb，s（Ib，s）的最大值- ■cb，s（Ib，s）对于所有可实现的供应量Ib，s。我们仅就如何快速计算这些值做出简要评论：最简单的事情总是有效的，就是详尽地列举可能的Ib，s（如果我们假设它是有限的）。一次，b，沙-■cb、sare凹函数inIb、swe可以使用嵌套区间更精确地计算最大值。因为我们必须使用至少一种批次类型，我们假设δi≥ 0时，与轨道t相关的ISPO目标函数的成本由（34）Xe确定∈EProb（e）-δ+Xb∈BXs∈S^λe，tb，S.使用第4小节中的一般方法。1.我们还可以对总体供应进行限制（我们假设凸度条件满足，我们的设置就是这样）。这里，V是分支和大小的对（b，s），A是由一个元素组成的使用集合，b是大小为s的分支b的可能供应Ib和b的集合。进一步收紧上限的另一种可能性是将分支必须以一定的多样性使用批次ty pes供应的事实结合起来。因此，在初始化阶段，可以分别计算每个分支的局部最佳匹配批次类型和多样性。

如果地块类型和可能的多重性的数量足够小，那么这可以通过穷举枚举来实现。对于基于适用批次类型集合的适当参数化的更复杂方法，我们参考[15]。然后，通过使用第4.1小节中的算法，可以合并对整体供应的限制，其中V是分支B的集合，A是批次类型s L的集合，B是多重性M的集合。换言之，我们放宽了对一定数量不同批次pes的限制，忽略了相应的成本。在我们的具体应用中，我们使用了上述三个上界。因此，我们的计算结果依赖于凸性；在所有其他情况下，算法只能使用第一个界限，通常速度较慢。4.3. Wo rkhorse 3：尺寸优化问题的启发式算法。在[11]中，针对批次类型设计问题（LDP）提出了所谓的分数-固定-调整（SFA）启发式算法。自民党与ISPOW的SOP阶段密切相关，有固定的情景和固定的降价策略。为了将SFA应用于停止阶段，我们需要修改SFA以应对批次类型的打开和处理成本。例如，这可以通过适当修改普通LDP的成本系数来实现：将处理成本纳入LDP的成本系数，只需添加处理成本cb，l,M以xb的成本系数计算，l,m、 对于每种可能数量的标段类型1到κ，可以通过使用规定数量的已用标段类型来求解单个LDP，将相应的开盘成本添加到最优目标函数中，并在事后选择最佳选项，从而考虑标段类型c的开盘成本。12 M.基斯林、S.库尔兹和J。

为了完整性，我们以特殊形式简要描述了LDP的SFA启发法的基本思想，我们在SOP阶段随时使用它。对于每个牧场，我们确定了三种当地最佳配置地块类型，最佳配置地块类型加100分，次优配置地块类型加10分，次优配置地块类型加1分，次优配置地块类型加1分。（当然，这可能会影响到最适合的批次类型和不同的评分模式。）有了这个，我们就隐式地为每一个批次类型l签署了一个分数∈ 五十、 大多数地段类型的得分为零。我们可以通过对单个分数求和，将这个循环推广到L的k-子集，从而隐式地得到L的n阶|L|k许多可行的彩票组合。这样，我们就可以按降序遍历L的k-子集，其中一个结可以任意断开。（关键的观察结果是，这可以在不事先明确生成所有此类子集的情况下实现。）在筛选步骤中，我们假设适用的批次类型仅限于L的当前k子集。现在我们可以应用第n4子类中的算法。1.在初始化中，我们从批次类型和多样性的局部最优分配开始。我们选择V=B，A=L，B=M。我们注意到，SFA启发式算法在实际情况下可靠地产生接近最优的解，见[11]。4.4。Wo rkhorse 4：尺寸优化问题的精确解。对于给定的情景e和给定的价格轨迹t，ISPO被简化为具有修改的共同成本系数的LDPO。例如，这个子问题可以通过使用第3节中给出的ILP公式的限制版本来解决，我们这样做是为了获得本文中的计算结果。

对于更复杂的算法，我们参考[15]，其中有一个定制的分支和价格算法，可以处理数百万种批次类型。4.5. Wo rkhorse 5：价格优化问题m的精确解。对于给定的场景e、给定的降价策略t和给定的初始供应量B，对于所有分支机构和规模，我们可以轻松计算每个分支机构、规模和周期的售出商品数量。由于在任何合理的设置下，除残值外的所有价格都是正的，因此我们得出结论，在任何最优解决方案中，售出商品的数量恰好是每个周期内库存和需求的最小值。由此，可以计算第3节中POP的ILP公式的所有其他因变量。因此，我们可以通过穷举可能的降价策略来解决POP阶段。这可以通过O（|B |·| S | | | K | | T |）步骤完成，这在所有实际情况下都是可能的（|B |≈ 1 000,3 ≤ |S|≤ 7、|K |=13、|T |=1820）到目前为止我们已经遇到了。4.6. 一个精确的分支定界算法。在本小节中，我们提出了一种主要算法——一种定制的分支定界算法。我们分为“地图”场景7→ 价格轨迹”。然后，深度j处的节点对应于所有这样的贴图，其中第一个j的图像是固定的。树叶是所有场景的固定图像地图。叶的成本可以通过解决第4节的anLDP问题来计算。4（工作区SE4），具体取决于第4.1节（工作区1）的方法。作为双重边界，我们使用第4.2小节（Workhorse 2）中的上界。作为原始边界，我们采用了第4小节中的启发式解。3（Workhorse 3），再次使用第4.1节（Workhorse 1）中的方法。

在分支步骤中，我们通过下一场景的所有可能价格轨迹，在节点中扩展部分定义的映射。在下文中，我们将详细介绍上述概念的实现。在初始化步骤中，我们使用子部分4中的算法计算每个场景e和每个价格轨迹ta的组合上界。2.为每对（e，t）保存绑定Γ（e，t），并可能在以后更新。使用这些边界，我们按升序标注价格轨迹：te，te | T |。接下来，我们在深度j的节点处考虑分支步骤，其中价格轨迹ξj∈ 对于第一个j情景，我们已经做好了准备。如果j<| e |，那么我们考虑s cenario j+1的可能价格轨迹。我们从i=1toi=|T |循环，并考虑价格轨迹tj+1i。现在我们计算上界jxh=1Prob（h）·Γ（h，ξh）+Prob（j+1）·Γ（j+1，tj+1i）+E | Xh=j+2Prob（h）·maxΓ（h，t）|t∈ T（35）对于第一个j+1价格轨迹固定为ξh的ISPO。如果该边界小于ISPO的最佳积分解，则我们可以修剪所有价格轨迹tj+1h≥ i、 否则，我们检查如何计算界Γ（j+1，tj+1i）。如果它是使用子节4中的组合松弛计算的。2，然后我们根据受限ILP模型计算LP界，参见第4小节。4，并可能更新界Γ（j+1，tj+1i）。如果更新后的上界（35）仍然很弱，无法修剪子树，则我们确定ξj+1=tj+1并继续下一个节点。在叶中，当所有价格轨迹都确定时，我们解决了剩余价格，见第4.4.4.7小节。乒乓球启发。由于精确算法的速度还不足以满足日常生产（见第6.1节），我们开发了一种快速启发式算法。