综合规模和价格优化问题

分支b中k期的（分形）平均收益率和价格组合p（k）产生的规模由yieldk，b，s（p）=πp（k）Salsek，b，s（p）给出。价格的每一次变动都会产生1u的成本。目标是确定第一阶段的决策，以便在每种情况下，对于最佳的第二阶段决策，预期利润最大，即总产量减去批次处理成本减去批次类型开放成本减去减价成本。我们将这种带追索权的两阶段随机优化问题称为综合规模和价格优化问题（ISPO）。备注1。部分存货、销售和需求被解释为预期存货的近似值。原则上，我们可以使用多（整体）需求场景和整体库存记账。然而，在一个高工资国家，必要数量的减少是从一个低工资国家开始批量交货的原因。6 M.KIESSLING、S.KURZ和J.Rambausencarios对这样一个模型的支持将是巨大的。因此，我们的场景只模拟了本文总体成功所引起的总需求的变化。它们不会对实际需求在周期、分支和规模方面的可变性进行建模。通过使用表示预期值近似值的分数来忽略这些变量。在这些情况下，我们说的是平均值，而不是预期值，以便将分数表示的预期值与我们在所有成功场景中明确计算的预期值区分开来。3.建模在下面，我们开发了扩展形式的ISPO确定性等价物的ILP公式。对于第一阶段（SOP），我们使用二进制赋值变量xb，l,mto编码独立的分配决定l（b）=l m（b）=m。

在第二阶段，我们为独立的第二阶段ass ignmentdecision pe（k）引入二进制赋值变量。为了计算利润和成本，我们需要更多的依赖变量。我们先列出完整的模型，然后再评论细节。最大值-Xb∈BXl∈LXm∈Mxb，l,m·cb，l,M-κXi=1δi·zi（1）+Xe∈EProb（e）Xk∈Kexp(-ρk）Xb∈BXs∈斯雷克，b，s- uknek（2） 尺寸优化阶段（SOP）：Xl∈LXm∈Mxb，l,m=1b（3）Xm∈Mxb，l,M≤ YlBl（4） Xl∈利索l≤κXi=1zi（5）zi≤ 子-1.i（6）Ib，s=Xl∈LXm∈嗯·ls·xb，l,Mb、 s（7）I=Xb∈BXs∈兄弟姐妹，s（8）I∈ [I，I]（9）xb，l,M∈ {0, 1} Bl, m（10）yl∈ {0, 1} l（11） zi公司∈ {0, 1} i（12）Ib，s，i∈ Zb、 s.（13）通过初始库存进行耦合：Ib，s- ve0，b，s=0b、 综合规模和价格优化问题7价格优化阶段（POP）：Xp∈普克，p=1k、 e（15）uek，0=1k<kobs，e（16）uekmax，pmax=1e（17）uek-1，p+uek，p≤ 1.k、 e，p，p<p（18）nek≥ uek-1，p+uek，p- 1.k、 e，p，p6=p（19）vek-1，b，s- vek，b，s=Xp∈普韦克-1，b，s，pk、 b、s、e（20）Xp∈普韦克，b，s，p≤ 韦克，b，sk、 b，s，e（21）wek，b，s，p≤ uek，p·dek，p，b，sk、 b，s，p，e（22）rek，b，s=Xp∈PπP·wek，b，s，Pk、 b，s，e（23）uek，p∈ {0, 1} k、 p，e（24）nek∈ {0, 1} k、 p，e（25）wek，b，s，p≥ 0k、 b，s，p，e（26）vek，b，s≥ 0k、 b，s，e（27）雷克，b，s≥ 0k、 b、s、e（28）我们首先对SOP阶段模型进行了评论：我们通过等式（3）强制将批次类型和多重性分配给每个分支。为了解释批次类型的开始，我们引入了批次类型变量yl指示是否为批次类型l 当且仅当使用第i个新批次类型时，才使用值为1的批次类型计数变量。等式（4）保证yl= 1无论何时l分配给至少一个分支b。不等式（5）意味着使用的不超过κ型。不等式（6）规定zi=1意味着使用的LOT类型的数量至少为i。

我们使用另一个因变量Ib，SFO作为b区和s区的库存，等式（7）将该变量与分配决策联系起来。然后，总库存由另一个因变量I给出，由等式（8）计算，并通过不等式（9）强制保持在给定的范围内。所有独立变量都必须是二进制的，即se（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表示情景e中价格p在分支机构b和规模s期间的平均销售额。rek，b，s表示情景e中的平均产量8 M。s.KURZ，KIESSLING，以及分支b中的J.RAMBAUin周期k和场景e中的大小s（关于我们在此处使用分数变量的原因，请参见备注1）方程式（20）描述了股票价格从一个周期到另一个周期的变化。

不等式（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。