当前位置：首页 > news >正文

【两阶段鲁棒优化】利用列-约束生成方法求解两阶段鲁棒优化问题（Python代码实现）

news 文章来源：https://blog.csdn.net/Yan_she_He/article/details/130166936 2025/5/24 1:27:35

💥💥💞💞欢迎来到本博客❤️❤️💥💥

🏆博主优势：🌞🌞🌞博客内容尽量做到思维缜密，逻辑清晰，为了方便读者。

⛳️座右铭：行百里者，半于九十。

📋📋📋本文目录如下：🎁🎁🎁

目录

💥1 概述

📚2 运行结果

2.1 CCGKKT

2.2 CCGSD

2.3 SPKKT

2.4 SDSP

2.5 MP

🎉3 文献来源

🌈4 Python代码及文章

💥1 概述

文献来源：

本文提出了一种求解两阶段鲁棒优化问题的列约束生成算法。与现有的bender式切割平面方法相比，圆柱和约束生成算法是一个通用的过程，具有统一的方法来处理最优性和可行性。对两阶段鲁棒位置-运输问题的计算研究表明，该算法的执行速度快了一个数量级。

原文摘要：

In this paper, we present a column-and-constraint generation algorithm to solve two-stage robust optimization problems. Compared with existing Benders-style cutting plane methods, the column-and- constraint generation algorithm is a general procedure with a unified approach to deal with optimality and feasibility. A computational study on a two-stage robust location-transportation problem shows that it performs an order of magnitude faster.

鲁棒优化(RO)[4 - 6,12,9,10]是近年来处理数据不确定性的一种优化方法。因为它的导出是为了对冲输入数据中的任何扰动，所以(单级)反渗透模型的解往往过于保守。为了解决这一问题，引入并研究了两阶段反渗透(以及更通用的多级反渗透)，也称为鲁棒可调或可适应优化，其中第二阶段问题是在第一阶段决策做出并揭示不确定性之后对决策建模。由于建模能力的提高，两级反渗透已经成为一种流行的决策工具。应用包括网络/运输问题[1,16,13]，投资组合优化[17]和电力系统调度问题[21,15,8]。

然而，两级反渗透模型的计算非常困难。

如[3]所示，即使是一个简单的两级RO问题也可能是np困难的。为了克服计算负担，研究了两种求解策略。第一种是使用近似算法，这种算法假设第二阶段的决策是不确定性的简单函数，例如仿射函数;参见[7]中的示例。第二类算法寻求按照Benders分解方法推导精确解，即利用第二阶段决策问题的对偶解逐步构造第一阶段决策的值函数[19,21,8,15,13]。我们称之为本德斯-对偶切割平面算法。

在[21]中，我们采用不同的切割平面策略来解决风力供应不确定的电力系统调度问题。该策略不使用第二阶段决策问题的对偶解来创建约束;相反，它在确定的场景的原始空间中动态地生成约束与资源决策变量，这与宾德斯-双过程背后的哲学非常不同。因此，它在[21]中被表示为原始切割算法，但实际上它是一个列-约束生成过程。在这项研究中，我们开发并提出了这个求解程序，在一个通用的设置和基准的弯曲双切割平面程序。

在列-约束生成过程中，生成的变量和约束与两阶段随机规划模型中的变量和约束非常相似。此外，当不确定性集是离散的和有限的，通过枚举集中每个场景的变量和约束，可以构造一个等效的整体优化公式[17]。然而，据我们所知，除了[21]中的工作外，还没有报道过在切割平面过程中使用这些变量和约束来解决两级RO问题的算法。这是该切割平面算法在一般设置中的第一次介绍，并首次从理论上和系统地比较了其与bender -dual切割平面方法的性能。