MATLAB代码：基于列约束生成法CCG的两阶段鲁棒问题求解 关键词：两阶段鲁棒 列约束生成法 CCG算法 鲁棒优化 参考文档：《Solving two-stage robust optimization problems using a column-and-constraint generation method》 仿真平台：MATLAB YALMIP+CPLEX 优势：代码注释详实，适合参考学习，非目前烂大街的微网两阶段规划版本，请仔细辨识！ 主要内容：代码构建了两阶段鲁棒优化模型，并用文档中的相对简单的算例，进行CCG算法的验证，此篇文献是CCG算法或者列约束生成算法的入门级文献，其经典程度不言而喻，几乎每个搞CCG的两阶段鲁棒的人都绕不过此篇文献，所以萌新们或者新手们赶紧冲起来学习吧！ 这段程序主要是一个优化问题的求解过程，涉及到主问题和子问题的求解。下面我将对程序进行详细的解释和分析。 首先，程序的开头使用了一些命令来清除变量、关闭窗口等。然后，定义了一些参数和变量，包括不确定性参数d、主问题参数MP、子问题参数SP、KKT参数和优化器设置opt。 接下来，程序进入主问题求解的过程。主问题的目标是最小化MPFunc + theta，其中MPFunc是一个关于MP.Y和MP.Z的函数，theta是一个变量。主问题的约束包括MPconstrains、theta >= SPFunc、SPconstrains和dconstrains。其中，MPconstrains是一个关于MP.Y和MP.Z的约束，SPFunc是一个关于MP、SP和d的函数，SPconstrains是一个关于SP.X的约束，dconstrains是一个关于d的约束。通过调用优化器，求解主问题，并将结果存储在result中。最后，将MPFunc + theta的值赋给LB。 然后，程序进入子问题求解的过程。子问题的目标是最大化-SPFunc，其中SPFunc是一个关于MP、SP、KKT和d的函数。子问题的约束包括SPconstrains、dconstrains和KKT的约束。通过调用优化器，求解子问题，并将结果存储在result中。最后，将SPFunc的值加上MPFunc的值赋给UB。 接下来，程序进入CCG（Cutting-Plane Generation）迭代过程。在迭代过程中，程序使用while循环，直到UB和LB的差的绝对值小于1e-5为止。在每次迭代中，程序根据当前的UB和LB的值，更新SP的约束和MP的约束。然后，再次求解主问题和子问题，并更新UB和LB的值。迭代次数n加1。 最后，程序定义了几个子函数，包括MPParams、MPconstrainsAndFunc、SPParams、SPConstrainsAndFunc、KKTParams、SPKKT和UncertaintySet。这些子函数分别用于定义和计算主问题和子问题中的参数、约束和目标函数。 综上所述，这段程序主要是一个优化问题的求解过程，通过迭代的方式不断更新UB和LB的值，直到收敛为止。程序涉及到的知识点包括优化理论、线性规划、对偶问题、不确定性建模等。通过对程序的分析和理解，可以了解优化问题的求解过程和相关的数学理论。

概述

本文档旨在详细说明一个基于 列约束生成法（Column-and-Constraint Generation, CCG） 的两阶段鲁棒优化问题求解器的实现逻辑与功能架构。该实现以经典文献为基础，采用 MATLAB 语言结合 YALMIP 建模工具包构建，适用于处理具有不确定参数的两阶段决策问题。其核心思想是通过迭代主问题（Master Problem, MP）与子问题（Subproblem, SP）之间的信息交换，逐步收紧可行域，最终收敛至鲁棒最优解。

该求解器不仅结构清晰、逻辑严谨，而且具备良好的可扩展性，适合作为教学示例或进一步研究的起点。

---

问题建模背景

本代码解决的是一类典型的 两阶段鲁棒优化问题，其数学形式可概括为：

\[

MATLAB代码：基于列约束生成法CCG的两阶段鲁棒问题求解 关键词：两阶段鲁棒 列约束生成法 CCG算法 鲁棒优化 参考文档：《Solving two-stage robust optimization problems using a column-and-constraint generation method》 仿真平台：MATLAB YALMIP+CPLEX 优势：代码注释详实，适合参考学习，非目前烂大街的微网两阶段规划版本，请仔细辨识！ 主要内容：代码构建了两阶段鲁棒优化模型，并用文档中的相对简单的算例，进行CCG算法的验证，此篇文献是CCG算法或者列约束生成算法的入门级文献，其经典程度不言而喻，几乎每个搞CCG的两阶段鲁棒的人都绕不过此篇文献，所以萌新们或者新手们赶紧冲起来学习吧！ 这段程序主要是一个优化问题的求解过程，涉及到主问题和子问题的求解。下面我将对程序进行详细的解释和分析。 首先，程序的开头使用了一些命令来清除变量、关闭窗口等。然后，定义了一些参数和变量，包括不确定性参数d、主问题参数MP、子问题参数SP、KKT参数和优化器设置opt。 接下来，程序进入主问题求解的过程。主问题的目标是最小化MPFunc + theta，其中MPFunc是一个关于MP.Y和MP.Z的函数，theta是一个变量。主问题的约束包括MPconstrains、theta >= SPFunc、SPconstrains和dconstrains。其中，MPconstrains是一个关于MP.Y和MP.Z的约束，SPFunc是一个关于MP、SP和d的函数，SPconstrains是一个关于SP.X的约束，dconstrains是一个关于d的约束。通过调用优化器，求解主问题，并将结果存储在result中。最后，将MPFunc + theta的值赋给LB。 然后，程序进入子问题求解的过程。子问题的目标是最大化-SPFunc，其中SPFunc是一个关于MP、SP、KKT和d的函数。子问题的约束包括SPconstrains、dconstrains和KKT的约束。通过调用优化器，求解子问题，并将结果存储在result中。最后，将SPFunc的值加上MPFunc的值赋给UB。 接下来，程序进入CCG（Cutting-Plane Generation）迭代过程。在迭代过程中，程序使用while循环，直到UB和LB的差的绝对值小于1e-5为止。在每次迭代中，程序根据当前的UB和LB的值，更新SP的约束和MP的约束。然后，再次求解主问题和子问题，并更新UB和LB的值。迭代次数n加1。 最后，程序定义了几个子函数，包括MPParams、MPconstrainsAndFunc、SPParams、SPConstrainsAndFunc、KKTParams、SPKKT和UncertaintySet。这些子函数分别用于定义和计算主问题和子问题中的参数、约束和目标函数。 综上所述，这段程序主要是一个优化问题的求解过程，通过迭代的方式不断更新UB和LB的值，直到收敛为止。程序涉及到的知识点包括优化理论、线性规划、对偶问题、不确定性建模等。通过对程序的分析和理解，可以了解优化问题的求解过程和相关的数学理论。

\min{y \in Y} \left\{ c^\top y + \max{d \in \mathcal{D}} \min_{x \in X(y,d)} q^\top x \right\}

\]

其中：

• 第一阶段变量 \( y \) 为“此处决策”（here-and-now），需在不确定性揭示前确定；
• 第二阶段变量 \( x \) 为“等待观察后决策”（wait-and-see），依赖于不确定参数 \( d \)；
• 不确定集 \( \mathcal{D} \) 为有界凸集（本例中为多面体）；
• 内层最坏情形下的第二阶段成本通过子问题建模。

由于直接求解此类 min-max-min 问题计算复杂度高，CCG 算法通过 主问题逐步添加最坏场景对应的约束，实现高效逼近。

---

整体架构与算法流程

求解器采用 主-子问题交替迭代 的框架，遵循标准 CCG 算法逻辑：

1. 初始化：构建初始主问题（含松弛变量 \(\theta\) 表示第二阶段成本上界）与不确定性集。
2. 主问题求解：在当前已知场景下，最小化第一阶段成本与 \(\theta\) 之和，获得下界（LB）。
3. 子问题求解：固定主问题解，求解最坏情况下的第二阶段问题（即最大化第二阶段成本），获得上界（UB）及对应最坏场景 \(d^*\)。
4. 约束生成：将该最坏场景下的第二阶段可行性约束（即“列”）加入主问题。
5. 收敛判断：若上下界差距小于预设容差（如 \(10^{-5}\)），则终止；否则返回第2步。

该过程确保每次迭代主问题可行域被收紧，上下界单调收敛。

---

核心模块解析

1. 主问题（Master Problem）模块

主问题负责第一阶段决策变量（如设施选址 \(Y\) 与产能分配 \(Z\)）的优化，并通过变量 \(\theta\) 对第二阶段成本进行保守估计。其约束包括：

• 投资-产能耦合约束（如 \(Zi \leq 800 Yi\)）；
• 总产能满足最低需求（\(\sum Z_i \geq 772\)）；
• \(\theta\) 不小于当前所有已知场景下的第二阶段最优值（通过迭代动态添加）。

目标函数为第一阶段固定成本与可变成本之和加上 \(\theta\)。

2. 子问题（Subproblem）模块

子问题在给定第一阶段决策 \(Z\) 和不确定需求 \(d\) 下，求解第二阶段运输或分配问题（变量 \(X_{ij}\)），目标是最小化运营成本。其约束包括：

• 非负性；
• 满足各需求点需求（\(\sumi X{ij} \geq d_j\)）；
• 不超过各供应点产能（\(\sumj X{ij} \leq Z_i\)）。

在 CCG 框架中，子问题被用于 寻找最坏需求场景，即最大化该最小成本。

3. 最坏场景识别：基于 KKT 条件的重构

为将子问题嵌入主问题的优化循环中，代码采用 KKT 条件线性化技术 将内层 min 问题转化为等价的混合整数线性约束（MILP）。具体包括：

• 原问题可行性约束；
• 对偶问题可行性约束；
• 互补松弛条件（通过大M法与二进制变量建模）。

这一技巧使得原本嵌套的 min-max-min 问题可被单层 MILP 求解器（如 CPLEX）处理，是实现 CCG 的关键。

4. 不确定性集建模

不确定需求 \(d = [d1, d2, d3]\) 被定义为基线值加上扰动项，扰动由辅助变量 \(g0, g1, g2\) 控制，并受以下约束：

• 各扰动非负且不超过1；
• 总扰动和不超过1.8；
• 前两项扰动和不超过1.2。

这构成一个多面体不确定集，符合鲁棒优化常用假设，兼顾保守性与实用性。

---

收敛性与数值实现

算法采用标准 CCG 收敛准则：当主问题下界（LB）与子问题上界（UB）之差小于 \(10^{-5}\) 时停止。每次迭代：

• 主问题提供可行解与成本下界；
• 子问题验证该解在最坏情况下的表现，并提供成本上界；
• 新增的“列”（即最坏场景下的第二阶段约束）确保主问题不再低估风险。

数值实验表明，该实现对中小规模问题收敛迅速，通常在数次迭代内完成。

---

应用价值与扩展方向

本代码虽以教学和验证为目的，但其结构具备良好扩展性：

• 可替换不确定性集为预算不确定集、椭球集等；
• 可扩展至多产品、多周期场景；
• 可集成割平面、加速启发式等改进策略；
• 可迁移至其他建模语言（如 JuMP、Pyomo）或求解器生态。

对于从事鲁棒优化、供应链设计、能源规划等领域的研究者与工程师，此实现提供了一个清晰、可靠的算法原型。

---

结语

该 CCG 求解器以简洁而严谨的方式实现了两阶段鲁棒优化的核心思想，兼顾理论正确性与工程可实现性。通过主-子问题协同、KKT 重构与动态约束生成，有效应对了不确定性下的决策挑战，是理解与应用列约束生成法的理想范例。