简介这份资源面向运筹优化方向的研究生、科研人员与工程实践者聚焦两阶段鲁棒优化中CCG列生成与Benders分解两类主流求解框架帮助读者在不确定环境下构建最坏情况性能可接受的决策模型。压缩包共5个文件含3份PDF与2份MATLAB源码整体约1.44MBPDF用于梳理Benders分解与列生成对比、算法综述及两阶段鲁棒问题求解思路m文件则给出可直接运行的代码案例便于对照论文复现。资源复现自原论文代码结构具备可扩展性读者可据此学习如何在MATLAB与YALMIP环境中搭建锥约束切割平面迭代流程理解切割平面逐步逼近最优解的机制以及Benders切割如何分离主问题与子问题、支持大规模问题的分布式求解。目前已有2285人学习下载适合希望强化模型求解能力、将鲁棒优化方法迁移到实际工程场景的读者参考。1. 两阶段鲁棒优化 CCG 与 Benders 代码包从论文复现到工程改编做电力调度、微网容量配置或者供应链选址的人迟早会撞上「不确定性」这堵墙。风光出力预测偏 10%最坏情况下调度方案直接不可行需求波动一放大原本算好的投资容量就绷不住。两阶段鲁棒优化就是冲着这个场景来的第一阶段先定「这里建多大、机组开不开」这类拍板就不能改的变量第二阶段等不确定性实现后再做补救决策目标是最坏情况下的总成本最小。这个压缩包里放的是 CCG列与约束生成和 Benders 分解两套 MATLAB YALMIP 实现外加三篇对比文献能直接跑、能改、能对着论文复现。适合已经会写 YALMIP 模型、但卡在「两阶段怎么迭代、对偶怎么推、切割怎么加」这一步的研究生和工程师。2. CCG 与 Benders 到底在切什么原理差异与选型判断2.1 两阶段鲁棒优化的标准型与「不确定集」的角色先把问题写成矩阵形式不然后面切割加在哪都说不清。标准两阶段鲁棒优化长这样min_y c^T y max_{u∈U} min_x d^T x s.t. Ay ≥ b Ex Gy ≥ h - Mu y ∈ Y, x ≥ 0y是第一阶段的「here-and-now」变量比如机组启停、储能容量x是第二阶段的「wait-and-see」变量比如实际出力、切负荷量u是不确定参数被约束在不确定集U里。外层max表示「挑最坏的不确定性」内层min表示「在最坏情况下做最优补救」。不确定集U的建模直接决定问题难度。常见三种盒式不确定集每个u独立取上下界最保守、预算不确定集Bertsimas-Sim限制同时偏离的个数用预算参数 Γ 调节保守度、多面体/数据驱动不确定集用历史数据包一个凸集。代码包里默认用的是预算型因为它在保守度和计算量之间最好调——Γ 取 0 退化成确定性取满就是盒式中间连续可调。提示不确定集写错是两阶段鲁棒优化最常见的翻车点。U如果不是凸集对偶变换那一步直接失效CCG 和 Benders 都跑不动。2.2 CCG 的「列」和 Benders 的「割」一个对偶两种视角CCG 全称 Column-and-Constraint Generation中文叫列与约束生成。它的核心思路是最坏情况的不确定性u*不可能遍历整个U那就先猜几个解一个只含有限场景的主问题再把子问题找出来的新u*对应的第二阶段变量和约束「整列」加进主问题。注意是「整列」——不仅加约束还加变量这是它和普通割平面最大的区别。Benders 分解走的是另一条路。它把问题拆成主问题只含y和子问题固定y后对u求最坏、对x求最优。子问题解完用它的对偶变量构造一个 Benders 割η ≥ 子问题目标的对偶表达式把η这个辅助变量从下方顶上去。割是加在η上的线性约束不加新变量。两者数学上等价工程上差别明显维度CCGBenders主问题规模随迭代增长快加变量约束增长慢只加约束子问题需对偶或直接枚举最坏场景必须对偶对偶变量要能取到收敛速度通常迭代次数少迭代次数多但每步轻实现难度中等场景管理要清晰对偶推导易错符号一错全崩适用不确定集小、场景可枚举大规模、子问题可并行我一般这么选不确定维度低于 20、场景能显式写出来用 CCG迭代 515 次基本收敛维度上百、子问题是标准 LP 且对偶好推用 Benders虽然迭代三五十次但每步求解快。代码包里两套都有正好可以对着同一算例比收敛曲线。2.3 从压缩包到可运行环境与文件对应关系解压后先别急着跑把文件认全。目录里通常有这么几类BendersAndCCG代码案例是主代码目录Solving two-stage robust optimization problems using a.pdf是 CCG 的原始论文Benders Decomposition vs. Column .pdf是两种方法的对比The Benders decomposition algorithm A literature review.pdf是 Benders 的综述。环境要求不复杂MATLAB R2018b 以上YALMIP 装最新版求解器至少有一个能解 MILP 和 LP 的——常见搭配是 Gurobi快或 Cplex没有商业求解器就用 GLPK 一个 LP 求解器凑合但大规模算例会慢到怀疑人生。YALMIP 的安装就是把解压出来的文件夹加到 MATLAB 路径然后yalmiptest看它认出了哪些求解器。% 检查 YALMIP 和求解器是否就位 addpath(genpath(C:\yalmip)); % 换成你的实际路径 yalmiptest; % 输出里能看到 gurobi/cplex/glpk 的状态 which sdpvar % 能返回路径说明 YALMIP 加载成功addpath(genpath(...))把 YALMIP 及其子目录全加进来yalmiptest会跑一串小测试并列出可用求解器which sdpvar是最快的自检——返回空就说明路径没配对。这一步过了再往下走否则后面报的错全是「未定义函数 sdpvar」跟算法本身没关系。3. CCG 主循环拆解主问题、子问题与场景管理3.1 主问题建模有限场景下的两阶段近似CCG 主问题只考虑当前已知的有限个最坏场景集合S。第一阶段的y是全局的第二阶段对每个场景s各有一套x_s% 主问题已知场景集 S 下的两阶段近似 y sdpvar(n_y, 1); x sdpvar(n_x, length(S)); % 每个场景一列 eta sdpvar(1); % 最坏情况成本的下界 Constraints [A*y b]; for s 1:length(S) u_s S{s}; % 第 s 个已识别的最坏场景 Constraints [Constraints, ... E*x(:,s) G*y h - M*u_s, ... x(:,s) 0]; end Constraints [Constraints, eta d*x(:,s) for s 1:length(S)]; % 注意上面这行是伪写法实际要循环累加 Objective c*y eta; optimize(Constraints, Objective, ops);x定义成矩阵而不是元胞是为了让 YALMIP 一次性把约束向量化求解快很多。eta是辅助变量代表「最坏场景下的第二阶段成本」主问题目标c*y eta就是在最小化「第一阶段成本 最坏补救成本」。每个场景的约束E*x(:,s) G*y h - M*u_s必须逐场景写全漏一个场景主问题就会给出一个偏乐观的下界。注意eta d*x(:,s)这类约束在 YALMIP 里不能写成列表推导老老实实 for 循环拼Constraints否则报维度错。3.2 子问题固定 y 后找最坏 u子问题是 CCG 的灵魂固定主问题解出来的y*在不确定集U里找让第二阶段成本最大的u。它是一个「max-min」结构通常用对偶把它转成单层 max 问题% 子问题固定 y_star求 max_u min_x d*x % 对偶后变成 max_{u, lambda} (h - M*u - G*y_star) * lambda lambda sdpvar(n_con, 1); SubCons [E*lambda d, lambda 0]; % 内层 min 的对偶约束 % 不确定集约束预算型示例 SubCons [SubCons, sum(abs(u)) Gamma, -u_max u u_max]; SubObj (h - M*u - G*y_star) * lambda; optimize(SubCons, -SubObj, ops); % 最大化 SubObj u_worst value(u);对偶推导的关键是内层min d*x s.t. Ex h - Mu - Gy它的对偶是max (h-Mu-Gy)*lambda s.t. E*lambda d, lambda 0。lambda就是对偶变量维度等于第二阶段约束条数。sum(abs(u)) Gamma是预算不确定集YALMIP 会自动线性化绝对值。optimize里目标取负号是因为 YALMIP 默认求最小。子问题解出来的u_worst就是这一轮新识别的最坏场景。如果子问题目标值也就是最坏成本和主问题里的eta差距小于容差说明主问题已经覆盖了真正的最坏情况收敛。3.3 收敛判据与场景加入上下界怎么夹CCG 的收敛靠上下界夹逼。主问题目标值是下界LB因为它只考虑了部分场景乐观子问题目标值是上界UB它找到了一个真实可行的最坏情况。每轮迭代LB value(Objective); % 主问题目标 UB c*value(y) value(SubObj); % 第一阶段成本 子问题最坏成本 gap (UB - LB) / abs(UB); if gap 1e-4 break; % 收敛 else S{end1} u_worst; % 把新场景加进主问题 endgap用相对误差比绝对误差稳因为成本量纲可能很大。1e-4是常用容差要求高可以到1e-6但迭代次数会明显增加。S{end1} u_worst就是「列生成」里加的那一列——新场景对应的第二阶段变量和约束下一轮会被主问题一起纳入。血泪经验如果gap在某个值附近反复横跳不下降八成是子问题的对偶写错了或者不确定集约束漏了边界。这时候别硬调容差回去检查E*lambda d的符号。4. Benders 分解落地对偶割的推导与代码实现4.1 主问题与辅助变量 η 的构造Benders 主问题比 CCG 干净因为它不加场景变量只维护一个辅助变量eta和一堆割y sdpvar(n_y, 1); eta sdpvar(1); Constraints [A*y b]; % 初始可以给 eta 一个下界避免无界 Constraints [Constraints, eta -1e6]; Objective c*y eta; optimize(Constraints, Objective, ops);eta是第二阶段最坏成本的估计。初始没有割的时候eta可以取负无穷但求解器不喜欢无界所以给个-1e6这种大负数兜底。每轮子问题解完加一个割eta就被从下面顶高一点直到它等于真实的最坏成本。4.2 子问题对偶与 Benders 割的生成Benders 子问题和 CCG 子问题形式一样都是固定y求max_u min_x。区别在于Benders 要把对偶解lambda*拿回来构造割% 子问题对偶求解同上 optimize(SubCons, -SubObj, ops); lambda_star value(lambda); u_star value(u); sub_val value(SubObj); % 生成 Benders 割eta (h - M*u_star - G*y) * lambda_star % 注意割里 y 是变量u_star 和 lambda_star 是常数 cut eta (h - M*u_star - G*y) * lambda_star; Constraints [Constraints, cut];割的推导来自子问题对偶目标(h - Mu - Gy)*lambda。在u u_star、lambda lambda_star处这个对偶目标关于y是线性的把它作为eta的下界约束加回主问题就是 Benders 最优割。如果子问题不可行要加的是可行性割feasibility cut形式类似但右边是可行性判据代码包里对这两种割都有分支处理。提示u_star和lambda_star必须用value()取成数值再写进割直接拿 sdpvar 写会变成非线性约束求解器直接罢工。4.3 迭代终止与数值容差设置Benders 的收敛判据和 CCG 一样用上下界LB value(Objective); UB c*value(y) sub_val; if (UB - LB) / abs(UB) 1e-4 break; end差别在于 Benders 迭代次数通常更多因为每个割只在一个点附近收紧eta。实际跑下来同一个算例 CCG 可能 8 次收敛Benders 要 30 次以上。但 Benders 每轮主问题规模几乎不变CCG 主问题会越来越胖。所以问题规模一大Benders 的总时间反而可能更短。数值容差还有个坑如果UB接近 0相对误差会炸。稳妥做法是gap (UB - LB) / max(abs(UB), 1)加个下限保护。代码包里默认用的是带保护的版本自己改的时候别把这层去掉。5. 避坑与排查跑不通时先看这几处5.1 现象迭代不收敛gap 卡在某个值不动原因通常是子问题对偶符号写反或者不确定集约束漏了。对偶约束E*lambda d里的不等号方向取决于原问题是还是推错一次 gap 就永远下不去。解决拿一个只有 2 个不确定变量的小算例手动枚举所有顶点验证子问题输出对上了再放大算例。5.2 现象主问题报 unbounded 或 infeasible原因多半是eta没有初始下界或者第一阶段约束A*y b本身矛盾。解决给eta加-1e6兜底把A*y b单独拿出来解一次可行性问题确认第一阶段可行域非空。另外检查y的整数性有没有声明binvar和sdpvar混用会导致约束维度错乱。5.3 现象求解器报「nonlinear constraint」但模型明明是线性的原因是对偶变量或场景参数没取数值sdpvar 混进了本该是常数的位置。解决所有从子问题带回主问题的量——u_star、lambda_star、sub_val——一律value()转数值。割里除了y和eta其他都必须是 double。5.4 现象CCG 主问题越跑越慢内存飙升原因是场景变量x按场景数线性增长场景一多矩阵维度爆炸。解决定期清理冗余场景目标值贡献低于阈值的场景可以合并或者切换到 Benders。另一个办法是把x定义成稀疏结构但 YALMIP 对稀疏 sdpvar 支持一般不如直接换方法。5.5 现象结果比确定性优化还差成本高得离谱原因是不确定集设得太保守Gamma取满了。解决把Gamma从 0 开始逐步加大画一条「成本 vs Gamma」曲线找到成本开始陡增的拐点那里通常是保守度和经济性的平衡点。工程上没人真按最坏最坏来都是按预算不确定集调。6. 进阶改编把代码包用到自己的算例上拿到代码包最忌讳的就是只跑通自带算例就完事。真正有价值的是把它改成你自己的问题。我一般按这个顺序动刀先换不确定集再换目标函数最后调求解器参数。换不确定集是最容易见效的改编。代码包默认是预算型如果你有历史数据可以换成数据驱动的多面体不确定集——用历史场景的凸包或者分位数包一个集合保守度比盒式低很多。改的时候只需要重写子问题里SubCons的不确定集约束部分主问题和割的逻辑完全不用动。% 数据驱动不确定集用历史数据的凸包约束 % U {u | u sum_k theta_k * u_hist(:,k), sum(theta) 1, theta 0} theta sdpvar(n_hist, 1); u sdpvar(n_u, 1); SubCons [SubCons, u u_hist * theta, sum(theta) 1, theta 0];u_hist是历史不确定场景矩阵每列一个场景theta是凸组合系数。这样u被限制在历史场景的凸包里比盒式紧得多算出来的成本更贴近实际。代价是子问题多了一组变量求解稍慢但通常值得。换目标函数也常见。原代码多半是最小化总成本你要是关心碳排放或者弃风率把Objective里的c*y eta换成加权形式就行权重用拉格朗日乘子法调或者直接画帕累托前沿。注意第二阶段目标d*x也要跟着改否则上下界对不上收敛判据失效。求解器参数这块Gurobi 用户把ops sdpsettings(solver,gurobi,gurobi.MIPGap,1e-4)设上MIP 间隙控制住能省不少时间。Cplex 对应的是cplex.mip.tolerances.mipgap。如果迭代中主问题 MILP 越来越难解可以设一个时间上限超时就接受当前次优解放进下一轮工程上完全可接受。最后说个验证习惯每次改完模型先拿确定性版本Gamma 0跑一遍结果应该和普通确定性优化完全一致。对不上就说明改动引入了 bug别急着跑鲁棒版本。这个自检我每次都走省下过无数次返工。从那以后我每次改编两阶段模型都强制先过一遍Gamma 0的确定性对照再逐步加保守度。希望帮到你。本文还有配套的精品资源点击获取
简介这份资源面向运筹优化方向的研究生、科研人员与工程实践者聚焦两阶段鲁棒优化中CCG列生成与Benders分解两类主流求解框架帮助读者在不确定环境下构建最坏情况性能可接受的决策模型。压缩包共5个文件含3份PDF与2份MATLAB源码整体约1.44MBPDF用于梳理Benders分解与列生成对比、算法综述及两阶段鲁棒问题求解思路m文件则给出可直接运行的代码案例便于对照论文复现。资源复现自原论文代码结构具备可扩展性读者可据此学习如何在MATLAB与YALMIP环境中搭建锥约束切割平面迭代流程理解切割平面逐步逼近最优解的机制以及Benders切割如何分离主问题与子问题、支持大规模问题的分布式求解。目前已有2285人学习下载适合希望强化模型求解能力、将鲁棒优化方法迁移到实际工程场景的读者参考。1. 两阶段鲁棒优化 CCG 与 Benders 代码包从论文复现到工程改编做电力调度、微网容量配置或者供应链选址的人迟早会撞上「不确定性」这堵墙。风光出力预测偏 10%最坏情况下调度方案直接不可行需求波动一放大原本算好的投资容量就绷不住。两阶段鲁棒优化就是冲着这个场景来的第一阶段先定「这里建多大、机组开不开」这类拍板就不能改的变量第二阶段等不确定性实现后再做补救决策目标是最坏情况下的总成本最小。这个压缩包里放的是 CCG列与约束生成和 Benders 分解两套 MATLAB YALMIP 实现外加三篇对比文献能直接跑、能改、能对着论文复现。适合已经会写 YALMIP 模型、但卡在「两阶段怎么迭代、对偶怎么推、切割怎么加」这一步的研究生和工程师。2. CCG 与 Benders 到底在切什么原理差异与选型判断2.1 两阶段鲁棒优化的标准型与「不确定集」的角色先把问题写成矩阵形式不然后面切割加在哪都说不清。标准两阶段鲁棒优化长这样min_y c^T y max_{u∈U} min_x d^T x s.t. Ay ≥ b Ex Gy ≥ h - Mu y ∈ Y, x ≥ 0y是第一阶段的「here-and-now」变量比如机组启停、储能容量x是第二阶段的「wait-and-see」变量比如实际出力、切负荷量u是不确定参数被约束在不确定集U里。外层max表示「挑最坏的不确定性」内层min表示「在最坏情况下做最优补救」。不确定集U的建模直接决定问题难度。常见三种盒式不确定集每个u独立取上下界最保守、预算不确定集Bertsimas-Sim限制同时偏离的个数用预算参数 Γ 调节保守度、多面体/数据驱动不确定集用历史数据包一个凸集。代码包里默认用的是预算型因为它在保守度和计算量之间最好调——Γ 取 0 退化成确定性取满就是盒式中间连续可调。提示不确定集写错是两阶段鲁棒优化最常见的翻车点。U如果不是凸集对偶变换那一步直接失效CCG 和 Benders 都跑不动。2.2 CCG 的「列」和 Benders 的「割」一个对偶两种视角CCG 全称 Column-and-Constraint Generation中文叫列与约束生成。它的核心思路是最坏情况的不确定性u*不可能遍历整个U那就先猜几个解一个只含有限场景的主问题再把子问题找出来的新u*对应的第二阶段变量和约束「整列」加进主问题。注意是「整列」——不仅加约束还加变量这是它和普通割平面最大的区别。Benders 分解走的是另一条路。它把问题拆成主问题只含y和子问题固定y后对u求最坏、对x求最优。子问题解完用它的对偶变量构造一个 Benders 割η ≥ 子问题目标的对偶表达式把η这个辅助变量从下方顶上去。割是加在η上的线性约束不加新变量。两者数学上等价工程上差别明显维度CCGBenders主问题规模随迭代增长快加变量约束增长慢只加约束子问题需对偶或直接枚举最坏场景必须对偶对偶变量要能取到收敛速度通常迭代次数少迭代次数多但每步轻实现难度中等场景管理要清晰对偶推导易错符号一错全崩适用不确定集小、场景可枚举大规模、子问题可并行我一般这么选不确定维度低于 20、场景能显式写出来用 CCG迭代 515 次基本收敛维度上百、子问题是标准 LP 且对偶好推用 Benders虽然迭代三五十次但每步求解快。代码包里两套都有正好可以对着同一算例比收敛曲线。2.3 从压缩包到可运行环境与文件对应关系解压后先别急着跑把文件认全。目录里通常有这么几类BendersAndCCG代码案例是主代码目录Solving two-stage robust optimization problems using a.pdf是 CCG 的原始论文Benders Decomposition vs. Column .pdf是两种方法的对比The Benders decomposition algorithm A literature review.pdf是 Benders 的综述。环境要求不复杂MATLAB R2018b 以上YALMIP 装最新版求解器至少有一个能解 MILP 和 LP 的——常见搭配是 Gurobi快或 Cplex没有商业求解器就用 GLPK 一个 LP 求解器凑合但大规模算例会慢到怀疑人生。YALMIP 的安装就是把解压出来的文件夹加到 MATLAB 路径然后yalmiptest看它认出了哪些求解器。% 检查 YALMIP 和求解器是否就位 addpath(genpath(C:\yalmip)); % 换成你的实际路径 yalmiptest; % 输出里能看到 gurobi/cplex/glpk 的状态 which sdpvar % 能返回路径说明 YALMIP 加载成功addpath(genpath(...))把 YALMIP 及其子目录全加进来yalmiptest会跑一串小测试并列出可用求解器which sdpvar是最快的自检——返回空就说明路径没配对。这一步过了再往下走否则后面报的错全是「未定义函数 sdpvar」跟算法本身没关系。3. CCG 主循环拆解主问题、子问题与场景管理3.1 主问题建模有限场景下的两阶段近似CCG 主问题只考虑当前已知的有限个最坏场景集合S。第一阶段的y是全局的第二阶段对每个场景s各有一套x_s% 主问题已知场景集 S 下的两阶段近似 y sdpvar(n_y, 1); x sdpvar(n_x, length(S)); % 每个场景一列 eta sdpvar(1); % 最坏情况成本的下界 Constraints [A*y b]; for s 1:length(S) u_s S{s}; % 第 s 个已识别的最坏场景 Constraints [Constraints, ... E*x(:,s) G*y h - M*u_s, ... x(:,s) 0]; end Constraints [Constraints, eta d*x(:,s) for s 1:length(S)]; % 注意上面这行是伪写法实际要循环累加 Objective c*y eta; optimize(Constraints, Objective, ops);x定义成矩阵而不是元胞是为了让 YALMIP 一次性把约束向量化求解快很多。eta是辅助变量代表「最坏场景下的第二阶段成本」主问题目标c*y eta就是在最小化「第一阶段成本 最坏补救成本」。每个场景的约束E*x(:,s) G*y h - M*u_s必须逐场景写全漏一个场景主问题就会给出一个偏乐观的下界。注意eta d*x(:,s)这类约束在 YALMIP 里不能写成列表推导老老实实 for 循环拼Constraints否则报维度错。3.2 子问题固定 y 后找最坏 u子问题是 CCG 的灵魂固定主问题解出来的y*在不确定集U里找让第二阶段成本最大的u。它是一个「max-min」结构通常用对偶把它转成单层 max 问题% 子问题固定 y_star求 max_u min_x d*x % 对偶后变成 max_{u, lambda} (h - M*u - G*y_star) * lambda lambda sdpvar(n_con, 1); SubCons [E*lambda d, lambda 0]; % 内层 min 的对偶约束 % 不确定集约束预算型示例 SubCons [SubCons, sum(abs(u)) Gamma, -u_max u u_max]; SubObj (h - M*u - G*y_star) * lambda; optimize(SubCons, -SubObj, ops); % 最大化 SubObj u_worst value(u);对偶推导的关键是内层min d*x s.t. Ex h - Mu - Gy它的对偶是max (h-Mu-Gy)*lambda s.t. E*lambda d, lambda 0。lambda就是对偶变量维度等于第二阶段约束条数。sum(abs(u)) Gamma是预算不确定集YALMIP 会自动线性化绝对值。optimize里目标取负号是因为 YALMIP 默认求最小。子问题解出来的u_worst就是这一轮新识别的最坏场景。如果子问题目标值也就是最坏成本和主问题里的eta差距小于容差说明主问题已经覆盖了真正的最坏情况收敛。3.3 收敛判据与场景加入上下界怎么夹CCG 的收敛靠上下界夹逼。主问题目标值是下界LB因为它只考虑了部分场景乐观子问题目标值是上界UB它找到了一个真实可行的最坏情况。每轮迭代LB value(Objective); % 主问题目标 UB c*value(y) value(SubObj); % 第一阶段成本 子问题最坏成本 gap (UB - LB) / abs(UB); if gap 1e-4 break; % 收敛 else S{end1} u_worst; % 把新场景加进主问题 endgap用相对误差比绝对误差稳因为成本量纲可能很大。1e-4是常用容差要求高可以到1e-6但迭代次数会明显增加。S{end1} u_worst就是「列生成」里加的那一列——新场景对应的第二阶段变量和约束下一轮会被主问题一起纳入。血泪经验如果gap在某个值附近反复横跳不下降八成是子问题的对偶写错了或者不确定集约束漏了边界。这时候别硬调容差回去检查E*lambda d的符号。4. Benders 分解落地对偶割的推导与代码实现4.1 主问题与辅助变量 η 的构造Benders 主问题比 CCG 干净因为它不加场景变量只维护一个辅助变量eta和一堆割y sdpvar(n_y, 1); eta sdpvar(1); Constraints [A*y b]; % 初始可以给 eta 一个下界避免无界 Constraints [Constraints, eta -1e6]; Objective c*y eta; optimize(Constraints, Objective, ops);eta是第二阶段最坏成本的估计。初始没有割的时候eta可以取负无穷但求解器不喜欢无界所以给个-1e6这种大负数兜底。每轮子问题解完加一个割eta就被从下面顶高一点直到它等于真实的最坏成本。4.2 子问题对偶与 Benders 割的生成Benders 子问题和 CCG 子问题形式一样都是固定y求max_u min_x。区别在于Benders 要把对偶解lambda*拿回来构造割% 子问题对偶求解同上 optimize(SubCons, -SubObj, ops); lambda_star value(lambda); u_star value(u); sub_val value(SubObj); % 生成 Benders 割eta (h - M*u_star - G*y) * lambda_star % 注意割里 y 是变量u_star 和 lambda_star 是常数 cut eta (h - M*u_star - G*y) * lambda_star; Constraints [Constraints, cut];割的推导来自子问题对偶目标(h - Mu - Gy)*lambda。在u u_star、lambda lambda_star处这个对偶目标关于y是线性的把它作为eta的下界约束加回主问题就是 Benders 最优割。如果子问题不可行要加的是可行性割feasibility cut形式类似但右边是可行性判据代码包里对这两种割都有分支处理。提示u_star和lambda_star必须用value()取成数值再写进割直接拿 sdpvar 写会变成非线性约束求解器直接罢工。4.3 迭代终止与数值容差设置Benders 的收敛判据和 CCG 一样用上下界LB value(Objective); UB c*value(y) sub_val; if (UB - LB) / abs(UB) 1e-4 break; end差别在于 Benders 迭代次数通常更多因为每个割只在一个点附近收紧eta。实际跑下来同一个算例 CCG 可能 8 次收敛Benders 要 30 次以上。但 Benders 每轮主问题规模几乎不变CCG 主问题会越来越胖。所以问题规模一大Benders 的总时间反而可能更短。数值容差还有个坑如果UB接近 0相对误差会炸。稳妥做法是gap (UB - LB) / max(abs(UB), 1)加个下限保护。代码包里默认用的是带保护的版本自己改的时候别把这层去掉。5. 避坑与排查跑不通时先看这几处5.1 现象迭代不收敛gap 卡在某个值不动原因通常是子问题对偶符号写反或者不确定集约束漏了。对偶约束E*lambda d里的不等号方向取决于原问题是还是推错一次 gap 就永远下不去。解决拿一个只有 2 个不确定变量的小算例手动枚举所有顶点验证子问题输出对上了再放大算例。5.2 现象主问题报 unbounded 或 infeasible原因多半是eta没有初始下界或者第一阶段约束A*y b本身矛盾。解决给eta加-1e6兜底把A*y b单独拿出来解一次可行性问题确认第一阶段可行域非空。另外检查y的整数性有没有声明binvar和sdpvar混用会导致约束维度错乱。5.3 现象求解器报「nonlinear constraint」但模型明明是线性的原因是对偶变量或场景参数没取数值sdpvar 混进了本该是常数的位置。解决所有从子问题带回主问题的量——u_star、lambda_star、sub_val——一律value()转数值。割里除了y和eta其他都必须是 double。5.4 现象CCG 主问题越跑越慢内存飙升原因是场景变量x按场景数线性增长场景一多矩阵维度爆炸。解决定期清理冗余场景目标值贡献低于阈值的场景可以合并或者切换到 Benders。另一个办法是把x定义成稀疏结构但 YALMIP 对稀疏 sdpvar 支持一般不如直接换方法。5.5 现象结果比确定性优化还差成本高得离谱原因是不确定集设得太保守Gamma取满了。解决把Gamma从 0 开始逐步加大画一条「成本 vs Gamma」曲线找到成本开始陡增的拐点那里通常是保守度和经济性的平衡点。工程上没人真按最坏最坏来都是按预算不确定集调。6. 进阶改编把代码包用到自己的算例上拿到代码包最忌讳的就是只跑通自带算例就完事。真正有价值的是把它改成你自己的问题。我一般按这个顺序动刀先换不确定集再换目标函数最后调求解器参数。换不确定集是最容易见效的改编。代码包默认是预算型如果你有历史数据可以换成数据驱动的多面体不确定集——用历史场景的凸包或者分位数包一个集合保守度比盒式低很多。改的时候只需要重写子问题里SubCons的不确定集约束部分主问题和割的逻辑完全不用动。% 数据驱动不确定集用历史数据的凸包约束 % U {u | u sum_k theta_k * u_hist(:,k), sum(theta) 1, theta 0} theta sdpvar(n_hist, 1); u sdpvar(n_u, 1); SubCons [SubCons, u u_hist * theta, sum(theta) 1, theta 0];u_hist是历史不确定场景矩阵每列一个场景theta是凸组合系数。这样u被限制在历史场景的凸包里比盒式紧得多算出来的成本更贴近实际。代价是子问题多了一组变量求解稍慢但通常值得。换目标函数也常见。原代码多半是最小化总成本你要是关心碳排放或者弃风率把Objective里的c*y eta换成加权形式就行权重用拉格朗日乘子法调或者直接画帕累托前沿。注意第二阶段目标d*x也要跟着改否则上下界对不上收敛判据失效。求解器参数这块Gurobi 用户把ops sdpsettings(solver,gurobi,gurobi.MIPGap,1e-4)设上MIP 间隙控制住能省不少时间。Cplex 对应的是cplex.mip.tolerances.mipgap。如果迭代中主问题 MILP 越来越难解可以设一个时间上限超时就接受当前次优解放进下一轮工程上完全可接受。最后说个验证习惯每次改完模型先拿确定性版本Gamma 0跑一遍结果应该和普通确定性优化完全一致。对不上就说明改动引入了 bug别急着跑鲁棒版本。这个自检我每次都走省下过无数次返工。从那以后我每次改编两阶段模型都强制先过一遍Gamma 0的确定性对照再逐步加保守度。希望帮到你。本文还有配套的精品资源点击获取
