随机整数规划 — 不确定性下离散决策的优化
- 提出者
- Dantzig, G. B.; Beale, E. M. L.
- 年份
- 1955
- 类型
- Optimization under uncertainty with discrete decisions
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
随机整数规划(Stochastic Integer Programming, SIP)是一种优化框架,它将整数(离散)决策变量与不确定性的显式概率建模相结合。它旨在寻找最佳的“此时此地”决策,以最小化未来情景分布中的预期成本(或最大化预期收益),同时考虑到某些决策必须在不确定性解决之前做出。
方法背后的直觉
许多实际决策既是离散的(建造或不建造设施;分配或不分配工人),又是不确定的(需求、成本和约束在决策时未知)。SIP 同时处理这两个挑战。它将不确定的未来建模为一组具有相关概率的情景,然后找到平均表现最佳的整数解——或者对最坏情况结果进行对冲的整数解。与随机线性规划不同,离散结构使问题在组合上更难,但产生的决策可以直接实施,无需舍入或近似。
历史学
随机规划可追溯到 Dantzig (1955) 和 Beale (1955),他们独立提出了不确定性下线性规划的两阶段追索模型。整数扩展随着整数规划在 1960 年代至 1980 年代成熟而出现。Birge 和 Louveaux 的 1997 年教科书对该领域进行了规范,Kleywegt 等人 (2002) 将样本平均近似(SAA)确立为大规模随机离散优化的标准计算方法。
何时使用
当决策本质上是离散的(二元选择、整单位分配、路由分配)并且关键参数在决策时是不确定的时,使用随机整数规划。它非常适用于产能规划、供应链网络设计、需求不确定性下的调度、能源调度以及具有随机产量的资源分配。当所有变量都是连续的(随机线性规划就足够了)、当不确定性可以忽略不计或在决策前完全可观察、当问题规模使得情景枚举在没有分解基础设施的情况下计算上不可行、或者当只有一个确定性情景相关时,请勿使用它。
局限与注意事项
- 计算复杂性随情景数量和整数变量数量的增加而迅速增长;大型实例是 NP 难的。
- 情景生成需要可信的概率分布,这可能难以从有限数据中获取或估计。
- 多阶段扩展(超过两阶段)面临情景树的指数增长,并且很少能超越三阶段。
- 需要建模技能才能正确指定追索可行性、非预期性约束和惩罚结构。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 显式建模不确定性而非使用点估计,从而产生对已实现情景具有鲁棒性的解决方案。
- 原生处理离散和二元决策,因此解决方案可以直接实施,无需事后舍入。
- 两阶段框架清晰地将战略性第一阶段决策与操作性第二阶段追索行动分开。
- 支持丰富的追索结构,包括资源采购、惩罚成本和纠正性调度。
- 统计质量界限(通过 SAA)允许从业者以量化置信度证明近似最优性。
应用
- 随机需求和提前期下的供应链网络设计
- 不确定可再生能源产出下的发电扩建规划
- 可变手术持续时间下的医院手术室调度
- 随机航班延误下的航空公司机组调度
- 灾害发生前人道主义物资的预先部署
- 具有离散资产选择和基于情景收益的金融投资组合优化
使用方式
使用方式
制定第一阶段问题:在不确定性揭示之前选择整数(或混合整数)决策变量 x。定义一个目标函数,其中包含即时成本和所有情景下的预期追索成本。在此处指定将 x 与可行性条件联系起来的约束。
公式
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]通过有限的情景集表示不确定性。每个情景为随机参数(需求水平、成本、资源可用性)分配特定值。情景可以通过历史抽样、从拟合分布中进行蒙特卡洛抽样或专家定义的代表性案例生成。每个情景都带有一个概率权重,所有权重之和为一。
在标准的二阶段公式中,在 x 固定且情景 xi 实现后,追索(第二阶段)问题确定纠正措施 y。追索问题通常是线性规划或整数规划。完整模型最小化 c^T x 加上预期追索成本 E[Q(x, xi)]。
公式
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)x求解情景子问题以评估给定 x 的每个情景的追索成本。技术包括分支定界法、Benders 分解、拉格朗日松弛和样本平均近似(Sample Average Approximation, SAA)方法。对于大型情景树,分解算法利用跨情景的块结构。
汇总子问题结果以估计预期追索成本。在 SAA 中,这是 S 个抽样情景的平均值。随着 S 的增长,由此产生的近似值收敛于真实期望。可以根据样本方差计算解质量的统计界限。
公式
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)通过最优性间隙、收敛准则或 SAA 的统计置信区间验证最优性或近似最优性。如果间隙不可接受,则细化情景集、增加样本量或收紧松弛。报告第一阶段解 x* 及其预期总成本。
常见陷阱
- 使用过少的情景会产生过于自信的解决方案;使用过多会使问题在计算上不可行——通过 SAA 收敛诊断进行平衡。
- 当第二阶段实际需要整数性时却忽略它,会导致乐观的成本估计和不可行的追索行动。
- 当参数相关时(例如,相关的需求和价格)却假设情景独立,会给预期成本估计带来系统性偏差。
- 在多阶段问题中忘记非预期性约束,会使模型利用在实践中无法获得的未来信息。
常见问题
随机整数规划与鲁棒优化有何不同?
SIP 最小化概率加权情景集中的预期成本,接受某些情景(如果可能性很小)可能导致高成本。鲁棒优化在不确定性集上最小化最坏情况成本,不作概率假设。SIP 需要概率分布;鲁棒优化只需要不确定性集。SIP 通常不那么保守,但对数据需求更大。
实践中需要多少情景?
这取决于问题维度和所需的精度。样本平均近似(SAA)方法提供了最优性间隙的统计置信区间。典型的应用研究使用数十到数千个情景;收敛诊断(界限估计量的方差)指导选择。对于结构化问题,情景削减技术(例如 Heitsch-Romisch)可以大幅减少情景数量。
随机整数规划能否处理多于两个阶段的问题?
可以,但多阶段 SIP 难度显著增加。情景树随阶段呈指数增长,并且必须在每个节点强制执行非预期性约束。在实践中,三阶段模型是可处理应用的常态;超出此范围,通常需要滚动时域或情景树削减等近似方法。
哪些软件可以求解随机整数规划模型?
常用求解器包括 CPLEX 和 Gurobi(通过 AMPL、Julia 中的 JuMP 或 Python 中的 PuLP/Pyomo 等代数建模语言),它们支持情景分解。专门的随机规划框架包括 PySP (Python)、SMPS 格式求解器和 Julia 包 StochasticPrograms.jl,后者实现了 SAA 和渐进式对冲。
随机整数规划与随机混合整数规划相同吗?
随机整数规划是更广泛的类别;随机混合整数规划(Stochastic Mixed-Integer Programming, SMIP)特指在某个或两个阶段中,某些变量是连续的而另一些是整数的模型。SMIP 是最通用且在实践中最常见的形式。
相关方法
参考文献
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ISBN:978-1-4614-0237-4已复制。Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.
打开 DOI 文献已复制。