文章链接：http://dx.doi.org/10.1016/j.orl.2013.05.003
01
研究背景
两阶段鲁棒优化模型是一种流行的决策工具，广泛应用于网络/运输问题、投资组合优化和电力系统调度问题等。然而，两阶段RO模型非常难以计算，即使是简单的两阶段RO问题也可能是NP难的。为了克服计算负担，文章给出了一种C＆CG算法，其在列和约束生成过程中，生成的变量和约束与两阶段随机规划模型中的变量和约束非常相似。此外，当不确定性集是离散和有限的时，通过枚举集合中每个场景的变量和约束，可以构造等价的整体优化公式。
02
模型介绍
文章给出了两阶段鲁棒优化模型的一般形式，其中y为第一阶段决策变量，x为第二阶段决策变量，并且可以取离散值或连续值。不确定性集U可以是离散集或多面体。
其中
为了解这个两阶段鲁棒优化模型，文章提出一种 C＆CG算法。首先给出C＆CG算法的主问题和子问题：
利用KKT条件，可以将SP2转化成：
03
算法框架
04
具体算例
文章以一个两阶段鲁棒选址运输问题为例来验证其算法有效性，首先给出了确定性模型：
其两阶段鲁棒选址运输问题的模型如下：
不确定集为：
具体参数如下：
不确定集为：
05
算法复现
使用Matlab2018a调用CPLEX求解器进行求解，首先展示其确定型模型的代码和结果：
其运行结果如下：
下面展示使用C＆CG算法求解对应两阶段鲁棒优化模型的代码和结果如下：
结果如下：
可以看到，使用C＆CG算法求解该两阶段鲁棒优化模型时，算法进行了两次迭代就收敛了，并且算法运行时间只有0.53秒，运行时间很短。
// 扫码获取本文算法代码
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
文章作者：东南数智港
责任编辑：张琪 马玺渊
微信编辑：疑疑
文章转载自『东南数智港』公众号，原文链接：算法复现|利用约束与列生成方法求解两阶段鲁棒优化问题
关注我们
FOLLOW US
