规模和价格综合优化问题

我们使用另一个因变量Ib、SFO来表示分支b中的库存和大小s，方程式（7）将该变量与分配决策联系起来。然后，总库存由另一个因变量I给出，由等式（8）计算，并通过不等式（9）强制保持在给定的界限内。所有独立变量必须是二进制的，即se e（10）到（12），而从属变量是整数（13）。接下来，让我们看看通过startinventories Ib连接到SOP阶段的POP阶段模型，该模型通过方程式（14）连接。等式（15）强制每个场景中每个时段只分配一个价格。起始价格和残值由方程式（16）和（17）表示。我们禁止按公式（18）涨价。独立二元变量nek表示周期k中的降价，如果价格与前一周期相比发生变化，则在不等式（19）中强制为1。以下限制使用一些相关变量对销售过程的动态进行建模。分数变量vek，b，s预测了场景e中分支机构b和规模k期间的平均库存水平。fr行动变量wek，b，s，p测量了s c enario e和rek，b，s期间分支机构b和规模s的平均销售额，以及s c enario e和rek，b，s的平均产量8 M.KIESSLING，s.KURZ，以及分支b中的J.RAMBAUin周期k和场景e中的大小s。（关于我们在此处使用分数变量的原因，请参见备注1。）方程（20）描述了股票价格从一个周期到另一个周期的变化。

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

这就产生了一个庞大而复杂的DILP，目前还不能用商业化的货架方法来解决。因此，在下一节中，我们将介绍一个精确的算法（相当快，但对于日常操作来说还不够快）和一个启发式算法（对于日常生产使用来说足够快，并且在所有实际测试中只有很小的最优性g AP）。4、ISPosite算法第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- 2最大值- 1.可行的降价策略或价格轨迹，即在我们的示例中= 1820每种情景的价格轨迹。分支步骤和边界步骤的确切细节在第4.6节中概述。

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

假设我们想要解决以下相当普遍的二元线性问题：minXv∈ VXa∈常闭触头∈Bψ（v，a，B）·xv，a，bXa∈常闭触头∈Bxv，a，b=1v∈ 五（29）十五∈ VXa∈常闭触头∈BД（a，B）·xv，a，B∈ [R，R]（30）xv，a，b∈ {0, 1} v∈ 五、 a∈ A、 b类∈ B、 （31）式中，（1）Д（a，B）在B中单调递增，（2）ψ（v，a，B）在B.10中是共凸的。KIESSLING，S.KURZ和J.Rambauth可以通过贪婪的方法解决这个问题的连续松弛：在初始化阶段，我们确定每个v∈ V和每个a∈ A最佳值bv，A∈ 使用二进制搜索，B具有最小代价ψ（v，a，B）。这个可以在O中找到一个|V |·| A |·日志（| B |）步骤。我们用v（a）表示元素a∈ A使ψ（v，A，bv，A）最小化，并通过v（b）使相应的值bv，v（A）最小化。这样，我们设置xv，v（a），v（b）=1表示所有v∈ 五、 所有其他值均设置为零。如果不等式（30）由纯偶然性满足，则xv、a、b变量的当前分配将产生全局最优解。否则，我们必须调整xv、a、bin顺序以满足资源建设。简而言之，我们只讨论以下情况：∈ VPa∈APb公司∈BИ（a，B）·xv，a，B>R。另一种情况类似。在这里，我们必须反复地从一些v∈ 五、 为此，我们引入了相对成本-v、 A对于每个v∈ V和每个备选方案a∈ A、 使用（32）βv（A）=max{b∈ B |Д（a，B）<Д（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 |Д（a，B）<Д（v（a），v（B））}= 我们将相应的相对成本设置为-v、 a=∞.

B yω（v）∈ A我们以较小的相关成本表示替代者-1v：=最小值{-v、 a | a∈ A} =-v、 ω（v）和v我们用V表示元素，其中ω（v），βv（ω（v））实现全球最小的相对成本。作为缩写，我们使用R=Pv∈ VД（V（a），V（b））和δ=Дv（a） ，v（b）-φω（v), βv（ω（v)). 由于目标函数的凸性，我们可以陈述如下：（a）如果-v= ∞, 那么这个问题就不可行了。（b） 如果R- δ ≥R、 然后在执行对的gre e e dily最优替换后v（a） ，v（b）通过ω（v), βv（ω（v))新的赋值对应于问题m的最优解，其中不等式（30）被PV取代∈ VPa∈APb公司∈BД（a，B）·xv，a，B≤ R- δ.（c） 如果R- δ<R我们利用新旧赋值的适当线性组合，得到了分数变量xv，a，bb的松弛问题的最优解。因此，在经过有限次迭代后，根据初始总体资源消耗a和R之间的差异，我们得到了问题的最优解，其中最多有两个分数变量xv、a、b。我们注意到，也可以通过使用abranch和bound方法来解算积分问题，我们在这里不详细讨论。4.2. Workhorse 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。分支b的批次类型为l，多重性为m，这会导致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集合（如果我们假设它是有限的）。一次rek、b、sand-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的集。进一步收紧上限的另一种可能性是将分支必须以一定的多样性使用批次ty pes供应的事实结合起来。因此，在初始化阶段，可以分别计算每个分支的局部最佳批次类型和多重性。

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

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

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