Skip to content
返回搜索结果

随机混合整数规划 — 在不确定性下具有离散和连续决策的优化

提出者
Birge, J. R.; Louveaux, F.; Sen, S.
年份
1990s–2000s
类型
Stochastic optimization model
类别
Simulation / optimization

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

随机混合整数规划 (Stochastic Mixed-Integer Programming, SMIP) 是一种优化框架,用于在成本、需求、产能等关键参数不确定并被建模为概率分布或一系列场景时,找到二元、整数和连续决策的最佳组合。它通过嵌入场景树或预期值目标来对冲不确定性,同时遵守组合约束,从而扩展了经典混合整数规划 (MIP)。

方法背后的直觉

许多实际规划问题都涉及是/否或整数选择——例如,是否建造一个设施,或分配整数数量的车辆——但未来是不确定的。SMIP 通过考虑一系列可能的未来场景并选择在不确定性揭示之前做出的第一阶段承诺(以最小化所有场景下的预期成本或最大化预期收益)来形式化这一过程。整数约束使得问题在组合上非常困难,但分解算法可以利用场景结构来处理大型实例。

历史学

随机规划起源于 Dantzig (1955) 和 Beale (1955) 的两阶段 LP。混合整数扩展在 1990 年代随着 Laporte 和 Louveaux (1993) 对整数追索的 L 形方法改编以及 Birge 和 Louveaux 1997 年教科书中的全面论述而突出。Sen 和 Higle 的 C3/D2 算法 (2005) 推动了可扩展 SMIP 求解器,将该领域确立为运筹学中一个成熟的学科。

何时使用

当决策涉及离散或二元选择(投资/不投资,开放单元的数量)且关键输入参数在可量化的概率分布下确实不确定时,使用 SMIP。适用于需求不确定下的供应链网络设计、电力容量扩张、医疗设施规划和灾难响应预置。

局限与注意事项

  • 计算复杂度随场景数量和整数变量的数量呈组合式增长;大型实例在没有有效分解的情况下可能难以处理。
  • 需要显式的概率分布或场景集——错误指定的模型会导致样本外表现不佳的解。
  • 两阶段模型可能过度简化多期决策;多阶段 SMIP 的难度显著增加。
  • 第二阶段的整数追索破坏了标准 Benders 割所利用的凸性,需要专门的整数 L 形割。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 在单一连贯的优化模型中处理不确定性下的组合离散决策。
  • 产生在所有场景下平衡预期性能的对冲第一阶段计划。
  • VSS 和 EVPI 指标为随机建模的价值提供了透明的理由。
  • 分解算法(L形法、渐进对冲法)可扩展至大量场景。
  • 在商业求解器(CPLEX、Gurobi)和建模语言(AMPL、Pyomo)中得到广泛支持。

应用

  • 具有不确定客户需求和二元设施选址决策的供应链网络设计。
  • 在不确定的可再生能源发电和负荷增长下的电力容量扩张规划。
  • 在流行病学不确定性下的医疗系统资源分配(整数员工、二元诊所开设)。
  • 在灾难场景发生前,人道主义物流的离散救灾物资预置。
  • 在市场不确定性下,具有交易成本和整数批量约束的金融投资组合优化。
  • 在不确定的航班延误下,具有二元分配变量的航空公司机组人员调度。

使用方式

使用方式

1

识别决策变量:在不确定性揭示之前做出的第一阶段决策 x(其中包含整数和/或二元变量),以及在场景 xi 出现后做出的第二阶段追索变量 y(xi)。指定目标系数、约束矩阵以及不确定参数的概率分布或离散场景集。

2

构建具有相关概率 {p_1, ..., p_S} 的有限场景集 {xi_1, ..., xi_S} 来近似底层分布。场景可以从历史数据、专家判断、拉丁超立方采样或矩匹配方法中导出。场景的质量直接影响解的质量。

3

构建确定性等价模型:最小化 c'x + sum_s p_s Q(x, xi_s),约束条件为第一阶段约束和整数约束。Q(x, xi_s) 是第二阶段价值函数——给定 x 和场景 xi_s 的追索行动的最优成本。组合规划是一个大型 MIP,其规模随场景数量的增加而增长。

公式
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}
4

使用分解算法求解 — L形方法(Benders分解)用于凸二次阶段,带有场景子问题的分支切割法,或用于场景并行分解的渐进对冲法。第二阶段的整数约束需要额外的割(整数L形割、提升-投影割)。现代求解器(CPLEX、Gurobi 配合回调函数,或 SMIP 特定库)实现了这些例程。

5

通过随机解价值 (Value of Stochastic Solution, VSS = EEV - RP) 和完美信息预期价值 (Expected Value of Perfect Information, EVPI = RP - WS) 来评估解,其中 RP 是追索问题的最优值,EEV 是使用确定性均值解的预期成本,WS 是观望价值。这些指标量化了显式建模不确定性的收益。

常见陷阱

  • 使用过少的场景会低估不确定性,产生过于自信的解;过多的场景则使模型在计算上不可行。
  • 混淆第一阶段和第二阶段变量的角色会导致模型无法正确反映信息揭示的时间顺序。
  • 依赖预期值解(忽略随机性)可能导致显著次优——务必计算 VSS 以证明 SMIP 的价值。
  • 在实际存在整数追索阶段的情况下忽略整数约束,会得到一个松弛模型,其解在实践中可能不可行。
  • SMIP 分解框架中的 MIP 求解器默认设置通常需要调整(分支优先级、割策略)。

常见问题

SMIP 与常规混合整数规划有何不同?

常规 MIP 在固定、已知参数下进行优化。SMIP 将不确定参数显式地建模为具有概率的场景集,在所有场景下优化预期性能,同时确保第一阶段决策在不确定性揭示之前做出。

我需要多少个场景?

没有普遍规则。对于某些问题,少至 10-50 个场景可能足以稳定第一阶段决策;其他问题则需要数千个。场景缩减技术和稳定性检验(检查最优解是否随添加更多场景而变化)有助于确定充分性。

什么是 L 形方法?

L 形方法是 Benders 分解法在随机规划中的应用。它通过迭代求解关于第一阶段变量的主 MIP 和场景子问题,添加最优性和可行性割到主问题中,直到收敛。对于整数追索,整数 L 形割取代了标准的 Benders 割。

何时应使用渐进对冲法而非 L 形方法?

渐进对冲法按场景而非子问题结构进行分解,非常适合并行计算。当场景数量多且子问题大,并且算法可以在集群上运行时,首选渐进对冲法。L 形方法通常更适用于场景较少、结构良好的情况。

SMIP 能处理多于两个阶段的情况吗?

可以,但多阶段 SMIP 需要一个场景树,该场景树在阶段数量上呈指数增长,并且分解变得更加复杂。实际上,大多数应用的 SMIP 模型使用两阶段,通过滚动视界或聚合来近似多期动态。

相关方法

参考文献

  1. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.

    ISBN:9780387982175
    已复制。
  2. Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.

    打开 DOI 文献
    已复制。