规模和价格综合优化问题

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

在第二阶段，我们为独立的第二阶段assignmentdecision pe（k）引入二进制赋值变量。为了计算利润和成本，我们需要更多的依赖变量。在对细节进行评论之前，我们列出了完整的模型。最大值-Xb公司∈BXl∈LXm公司∈Mxb，l,米·cb，l,M-κXi=1δi·zi（1）+Xe∈EProb（e）Xk∈Kexp(-ρk）Xb公司∈BXs型∈Srek，b，s- uknek（2） 尺寸优化阶段（SOP）：Xl∈LXm公司∈Mxb，l,m=1b（3）Xm∈Mxb，l,M≤ YlBl（4） X个l∈Ly公司l≤κXi=1zi（5）zi≤ zi公司-1.i（6）Ib，s=Xl∈LXm公司∈毫米·ls·xb，l,Mb、 s（7）I=Xb∈BXs型∈SIb，s（8）I∈ [I，I]（9）xb，l,M∈ {0，1}Bl, m（10）年l∈ {0，1}l（11） zi公司∈ {0，1}i（12）Ib，s，i∈ Zb、 s.（13）通过初始库存耦合：Ib，s- ve0，b，s=0b、 综合规模和价格优化问题7价格优化阶段（POP）：Xp∈Puek，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∈Pwek公司-1、b、s、pk、 b、s、e（20）Xp∈Pwek、b、s、p≤ vek，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）rek，b，s≥ 0k、 b、s、e（28）我们首先对SOP阶段模型进行了评论：我们通过等式（3）强制将批次类型和多重性分配给每个分支。为了解释批次类型的开始，我们引入了批次类型变量yl指示是否为批次类型l 当且仅当使用第i个新的批次类型时，才使用值为1的批次类型计数变量Z。等式（4）保证yl= 1无论何时l分配给至少一个分支b。不等式（5）表示使用的类型不超过κ个。不等式（6）规定zi=1意味着使用的lot类型的数量至少为i。

我们使用另一个因变量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）。第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、为了消除这些次要细节引起的一些并发症，我们假设我们通过直接使用对应的ILP公式来解决SOP子问题，请参见第4小节。4，不计算任何更便宜的界限。在第6节中，我们给出了所提出的brand和boundalgorithm的计算结果。作为一种启发式，也可以在分支和边界的开头使用，我们在第4小节中介绍了所谓的乒乓启发式。结果表明，它在只需要很少的计算时间的情况下，就可以获得非常好的解决方案质量。其基本思想是迭代求解尺寸优化和性能优化阶段的分离子问题。然后将一个子问题的临时解作为另一个子问题的输入。为此，我们提出了一种精确但相当简单的精确算法，用于子节4的有奖优化阶段。为了加速乒乓球，我们可以使用[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=1五、∈ 五（29）十五∈ VXa∈常闭触头∈BД（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中为协凸。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）^1v（a），v（b）- ^1a、 βv（a）每个资源项。如果{b∈ B |~n（a，B）<~n（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））和δ=Д五、（a） ，v（b）-^1ω（v), βv（ω（v)). 由于目标函数的凸性，我们可以陈述如下：（a）如果-五、= ∞, 那么这个问题就不可行了。（b） 如果R- δ≥R、 然后在执行对的gre e e dily最优替换后五、（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）启发式算法。LDP与ISPOW的SOP阶段密切相关，有固定的情景和固定的降价策略。为了将SFA应用于STOP阶段，我们需要修改SFA以应对批次类型的打开和处理成本。其次，这可以通过适当修改普通LDP的成本系数来实现：将处理成本纳入LDP的成本系数，只需添加处理成本cb，l,mto至xb的成本系数，l,m、 可通过使用规定数量的已用批次类型来解决每个可能数量的批次类型1到κ的单个LDP，将相应的期初成本添加到最优目标函数中，并在事后选择最佳选项，来考虑批次类型c的期初成本。12 M.KIESSLING、S.KURZ和J。