水电系统优化的拉格朗日松弛并行法

可在www.sciencedirect.com在线获取理论计算机科学电子笔记281（2011）101-111www.elsevier.com/locate/entcs水力发电系统优化的拉格朗日松弛并行法FannyGonza'leza，1，Lu'ısFarinaa，2，EustaquioMart'ıneza，3，Esteban Vargasa，4和Anastacio Arceb，5aFacultadPolit'ecnica-UniversidadNacionaldelEstebItaipu'BinacionalHernandarias -巴拉圭摘要本文介绍了拉格朗日松弛并行法在水电系统机组优化组合中的应用。 该模型是在一个集群上实现的低成本现成的个人电脑。并介绍了该平台所采用的算法。对一个相当重要的尺寸的样本问题的“加速”方面所得到的结果关键词：拉格朗日松弛并行，发电机组最优组合，个人计算机网络，集群。1引言拉格朗日松弛（LR）[14，15，7，12，9]是一种使用对偶理论的概念来处理问题的约束集考虑复杂的约束被转移到目标函数，这是评估通过特殊的惩罚参数称为拉格朗日乘子。因此，原始问题被转换为松弛问题，其中所得到的约束的结构生成子问题，这些子问题可以用更大的1电子邮件：fgonzalez@fpune.edu.py2电子邮件：lfarina@fpune.edu.py3电子邮件：amartinez@fpune.edu.py4电子邮件：evargas@fpune.edu.py5电子邮件：arce@itaipu.gov.py1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.11.028102F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101比原始的更容易。在[14，15，7]中，提出了一种求解TSP（旅行商问题）的精确算法，使用该算法获得了有希望的结果。后来，该技术被成功地用于解决其他组合优化问题[8，17，2]。LR技术也用于多个变量函数，这些变量函数可以在给定某些约束的情况下最大化或最小化。也可用于水热协调、优化操作等。[11，2]。优化水电系统中发电机组的组合问题[1，2]，特别是在经济学的背景下具有极大的兴趣。它涉及发电机组的适当编程，以使与发电损失相关的成本以及所述机组的启动和关闭成本最小化[1，2]。这个问题可以使用基于拉格朗日松弛和动态规划的启发式程序来解决，如[1]中所提出的。拉格朗日松弛法的求解过程是在两个层次上完成的，根据问题的大小，这两个层次由需要大量时间处理的对偶问题和原始问题定义。这方面的解决方法的基础上拉格朗日松弛justifies并行处理的技术应用研究，这项工作的主题[11，3]。本文按以下方式处理这个主题：第二节简要介绍拉格朗日松弛法，第三节讨论水电系统中机组的最优组合，第四节提出拉格朗日松弛并行法，第五节给出实验结果，以便介绍研究过程中所达到的结论。2拉格朗日松弛拉格朗日松弛，如[14，15]中所提到的，被用于实现TSP的精确算法，后来它被成功地用于解决其他问题。如[7，12，9]所述，LR被确立为一个强大的工具。在[13，23，28]中，可以找到有关LR技术的详细信息以及丰富的其他参考文献。总而言之，LR是一种使用对偶理论[18，27]中的概念以特殊方式处理给定问题的一组约束的技术。考虑复杂的约束被转移到目标函数，这是评估通过特殊的惩罚参数称为拉格朗日乘子。因此，一个原始问题被转换成一个放松的问题，其中所产生的约束的结构，在一般情况下，产生的子问题，可以更容易地解决比原始问题。考虑优化问题P，在这种情况下称为原始问题，在[28]中描述为：(1)min f（X）受制于：F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101103ΣΣ(2)h k（X）= e k，k = 1，2，...，M（3）gj（X）≤bj，j=1，2，.，p(4)x∈X其中函数f（X），gj（X） yhk（X）可以是任意非线性或非连续的[5]的文件。问题的可行域由约束（2）、（3）以及包括完整性和非负约束的其他约束限定，这里由集合X表示。假设在没有约束的情况下，该问题将容易地被解决（2）。拉格朗日松弛法放松约束h k（X）= e k，将它们移动到具有其对应乘子uk的目标函数，k = 1，2，.，m，这导致函数[5，18，28]：（五）ML（X，u）=f（X）+uk（ek−hk（X））k=1其中，u =（u1，u2，.，u m）T和u1，u2，...，u m被指定为Lagrange Mul-双变量（Dual Variables）可以观察到，如果放松的约束j是类型等式约束不受限制的拉格朗日乘子被链接[28]。对偶函数定义为：(6)Θ（u）=min× L（X，u）受制于：（7）gj（X）≤bj，j=1，2，.，p表达式（6）称为拉格朗日子问题。双重功能是Ob-在约束（3）和（4）下保持最小化拉格朗日函数。然后，问题的对偶函数被公式化为[28]：（八）（九）哪里maxΘ（u）服从：uk∈RmM（十）Θ（u）=min{f（X）+uk（ek−hk（X））}k=13水电系统机组的最优组合水力发电系统的发电机组的最优组合[1]可以采用评估发电系统中的损失以及与发电机组的启动和关闭相关的成本的模型作为性能标准机组组合问题的形式是一个混合整数104F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101我p=dT= T。美吉岛所以，这是一个不确定的问题[1]。除了前面提到的特征之外，非线性和问题的巨大规模使得实现最优解更加困难[1]。为了解决这个问题，在[1]中提出了一种启发式方法，该方法将问题分解为两个子问题：发电机组的承诺（CU），其确定在每个时间间隔期间每个发电厂中运行的发电水力机组的配置[2];以及对应于发电承诺（CG）的承诺，其确定给定操作中发电机组配置的最佳发电承诺。这两个子问题都可以迭代求解，直到得到系统图1提出了这种推理。图1.一、求解最优承诺问题的启发式方法图[1]3.1承诺生成问题水力发电机组的子问题CG可以被公式化为水力发电问题的特殊情况，其中运行中的发电机组的数量已经通过子问题CU建立。因此，前面提到的子问题的数学公式是：T N（十一）min ΣΣ{cp.fi(n∗it,pt)}（十二）t=1i =1受制于：Nt t我（十三）i=1T不我F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101105我我我我我（十四）t=1pmin（n<$t）≤pt≤pmax（n<$t）其中：T是时间间隔的数量;N是水力发电厂的数量;106F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101我我我⎩Σ⎨⎧⎨Σ⎩Σ我不t=1pt;N+1≤k≤N +T我我我我我我我我k=1k=1fi（pt，nt）是发电厂i[MW]中损耗的函数，取决于我我在时间间隔t期间发电单元的数量n和发电功率p;mi是水力发电厂i的功率目标[MW平均];dt是在时间间隔t[MW]期间系统的负载;恩吉是发电厂i在时间内运行的发电机组的数量间隔测试;cp与发电系统有关的损失成本;pt在时间t期间发电厂中产生的功率;p min（. ），p max（. ）最小和最大功率，分别与n产生我我在时间t期间，发电厂i中承诺的单元;这个问题涉及连续变量，可以通过拉格朗日松弛法[19，4，20，5]解决。 观察方程（11）至（14），可以指出，目标函数由与每个发电厂的发电相关联的并且针对每个时间间隔t的损耗函数的总和形成。这些函数是凸的，由二次多项式表示方程（1）至（10）与第2节中给出的方程之间的关系可以通过表达式（11）至（14）建立，考虑到（15）X = p t=[p（i，t）] N×T; i = 1，2，.， N; t = 1，2，...， 不和目标函数T N（16）f（X）=f∈{cp.fi（n∈it，pt）}具有等式约束t=1i =1联系我们（十七）hk（X）=pt; 1≤k≤N（十八）ek=t; 1≤k≤NN+1≤k≤N +T不平等的约束(19)gj（X）=pt−pmin（n<$t）;j={i×t}(20)bj=pmax（n<$t）−pmin（n<$t）;j={i×t}拉格朗日乘子（Dual Variables）(21)uk=不t=1Ni=1λt; 1≤k≤Tμi;T+1≤k≤N +T可以得到(22)L（X，u）=L（p，μ，λ）M m（23）f（X）+ukek−ukhk（X）i=1F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101107联系我们t=1Σ我p我我t=1t=1i=1我我我我我我我我我t=1i =1t=1t=1i=1t=1可以写成ΣTΣN（二十四）t=1.cp.fi（nt，pt）n+nTλt dt−Tλtpt+Ni=1这导致μt mi.T−TNi=1Mμi pt（二十五）和f（X）+uk（ek−hk（X））k=1T N N N T(26)好吧cp.fi（nit，pt）<$+<$λt（dt−<$pt） +<$μt（mi.T−<$pt）则对偶函数被定义为min XL（X，u）=mintL（p，μ，λ）我（二十七）S.T.S.T.gj（X）≤bj， j=1，2，.，p pmin（n<$t）≤pt≤pmax（n<$t）;最后，问题（11）至（14）的解可以通过求解以下对偶问题来获得：（二十八）maxΘ（u）=max h（μ，λ）S.T.S.T.u∈Rmλ∈RT，μ∈RN如前所述，问题的解决方案可以通过具有两个级别的分层计算结构来实现，根据[1]。在上层（协调器或主程序）中，拉格朗日乘子的值被确定，并且在下层中，根据协调器设置的拉格朗日乘子，针对每个发电厂和每个时间间隔解决原始子问题。图2中的块p（i，t）表示在时间间隔t期间连接到发电厂i的原始子问题的解。在这个层次上求解N×T个子问题，在协调器的上层确定μ和λ的值解决双重问题。3.2问题的序列解Σi=1108F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101优化问题的解决方案可以通过前面章节中提到的启发式方法获得，交替动态规划子问题CU和拉格朗日松弛子问题CG，直到使用图中描述的算法获得最佳解3.第三章。F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101109协调员图二、子问题CG的解的一般图[1]。开始求解子问题CU（使用动态规划）当发电机组的最后配置发生变化时，计算子问题CG（使用拉格朗日松弛法）计算拉格朗日乘子（λ，μ）对于t=1至T，解方程（27）计算误差（需求约束和目标功率误差）优化测试（发电和需求响应误差）如果没有找到解决方案，则再次计算子问题CG结束子问题CG。图三. 序贯求解算法。4并行拉格朗日松弛4.1平行接近如图2所示，对于特定情况，为了找到水电系统中发电机组的最佳投入，最好采用并行方法，因为可以同时进行计算要优化的水电系统由大量发电厂组成，对于所讨论的问题，可以建立不同的视野：短期，中期和长期，这意味着大量的计算。短期编程涉及每日离散化，中期编程涉及一周，长期编程涉及一年;然而，如果需要每日编程，则离散化应该是每小时，这允许对系统进行实际110F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101我时间[1]。规划和离散化范围显然定义了要处理的问题的大小，因为规划和离散化范围越大，数据量就越大在[11]中，并行环境被用来处理问题，它被认为是本文讨论的启发式方法并行化的动机然而，与上述建议中所提出的不同，这里实现的并行化是在子问题CG方面的拉格朗日松弛，以解决在由网络链接的工作站集群上实现主从模型4.2算法本工作中用于主处理器和从处理器的算法如下图所示，它们是根据负责中继消息的库MPITB [21]的主要通信指南编写的，通过Octave编程语言[22]实现主工艺：启动从属进程（MPI Init（））求解子问题CU（使用动态规划）当发电机组的最后配置发生变化时，做计算子问题CG计算拉格朗日乘子（λ，μ）对于k= 1to（K−1），发送（开关打开）到所有从属进程（MPI Send（））发送（λ，μ）到所有从进程（MPI Send（））对于k= 1至（K - 1），从所有从机接收pt（MPI Recv（））计算误差（需求和功率目标约束误差）优化测试（发电承诺和需求响应误差）如果没有找到解决方案，返回到计算子问题CG结束子问题CG计算子问题CU（获得发电机组的新配置对于k= 1至（K−1）发送（开关关闭）到所有活动的从进程（MPI Send（））结束（MPI最终确定）见图4。 Master进程的算法。在图4所示的算法中，主处理器将数据（μ，λ）发送到（K-1）个处理器，K对应于可用处理器的总数。主处理器发送命令以开始和完成发电计算;F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101111我我而它等待从属处理器的PT从进程：计算所必需的数值根据可用（初始和最终时间）接收来自主机的开关（MPI Recv（））当开关保持打开时，从主机接收（λ，μ）（MPI Recv（））对于初始时间到最终时间，计算公式（27）将pt发送到主进程（MPI Send（））从主机接收开关（MPI Recv（））端图五、从进程的算法如图4和图5所示，主进程和从进程在一定的时间间隔内解决了发电承诺的子问题，根据所建立的编程范围，将一部分时间分配给每个从进程5实验结果5.1计算环境图4和图5中的算法使用Octave编程语言[22]和来自Peli-canHPC架构[24]上的MPITB库（MPI ToolBox）[ 21 ]的指令进行编码，Peli-canHPC架构[ 24 ]即由个人计算机组成的工作站集群前面提到的集群由10台相同的计算机组成，配备2.2 GHzOpteron AMD处理器和1GB RAM内存，通过100 Mbps以太网网络互连，并与其他网络完全隔离。其中一台机器被选为主处理器，其他机器被选为从处理器。5.2结果通过一系列执行测试验证了并行化的性能，并将巴西水电系统中78个发电厂的每日编程范围使用的离散化是每小时。作为并行环境中的性能度量，使用了SpeedUp（Sp），其定义为：（二十九）Sp=tstp其中Ts对应于要求程序按顺序执行的时间（以秒为单位），Tp对应于在P个处理器上执行程序所需的时间。在图6（a）中，可以观察到，使用为解决发电承诺问题而提出的并行化方法，112F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101特别是从F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101113处理器加速比(a)（b）第（1）款见图6。 （a）加速（b）执行时间3 如果与仅使用一个处理器解决相同问题相比，则在时间方面获得收益。这种趋势是永久性的，当使用5个或更多处理器时，这一趋势更加明显。在图6（b）中，前面提到的可以通过检查多个处理器同时使用时执行时间相比之下，当顺序地解决优化问题时，如果与本提案中提出的并行化方法相比，则使用更多的时间，因为考虑到样本问题和所使用的实验平台，在6结论水电系统机组最优组合的优化问题，可以用拉格朗日松弛法和动态规划法相结合的启发式方法求解，也可以在并行环境中实现，因为它的目的是减少执行时间，符合实时控制的原则。 事实上，SpeedUp所呈现的增长趋势，以及解决问题的执行时间的下降趋势，鼓励其他并行算法的设计，可能比本文提出的更有效引用[1] A.，A.，“Despa c hoO 'timo de U nidades Geradorasem SistemasHidr o e l' etricosvia Heur 'ısticaBaseada em Relaxa c aoLagrangeanaeEschmacaoDinLagrangamica”，Ph.D. 论文，Uni vereducadeEstadualdeCampinas，巴西，2006年1月。[2] 阿尔斯·A T. Ohishi和S.苏文，电力系统中发电机组的优化调度，电力系统学报，第10卷。17（2002），第1期。处理器执行时间114F. 冈萨雷斯等人理论计算机科学电子笔记281（2011）101[3] Almeida 、 F.和 F.R odrguez ， “I n tr o ducci 'on a la programaci' on Escherela” ， Ed.ParaninfoCengageLearning，2008.[4] Bazaraa，S.和C.Shetty，[5] Bertzakas，D.，[6] De卡奥斯一集群，网址：http：//www.linux-magazine.es/issue/52/028-032Pelican\HPCLM52.pdf[7] 埃弗雷特三世资源最优配置。Res. 11（1963），399-417.[8] Fisher，M.，拉格朗日松弛法求解非线性规划问题，管理科学（1986年前），27（1981年），第1期，1-18页。[9] Fisher，M.，拉格朗日松弛法求解非线性规划问题，《管理科学》27（1981），第1期，第1-18页。[10] Fisher，M.，拉格朗日松弛法求解非线性规划问题，管理科学，50（2004），第10期。12，1861 -1871。[11] Fung，C.，S. Chow和K. Wong，第五次。2000年10月，第20届亚太电力系统控制与管理国际会议，香港[12] Geo Escherrion，A.， 整数规划，数学规划研究，2（1974），82-114.[13] Guignard，M.，“Lagrangean Relaxation”, TOP,[14] 赫尔德先生R. Karp，旅行商问题和最小生成树，运筹学，18（970），1138 -1162.[15] 持有M.，R. M. Karp，The Traveling Salesman Problem and Minimum Spanning Trees：Part II，Mathematical Programming，1（1971），No.1，6-25.[16] Hilera，J.，“Programaci'onEscherela”，Ed. Uni versidaddeAlcal'a，1998年。[17] Ji m'enez，N.，“Coordinacionhidrotermicaenelcortoplazomediantetecnicasderelajacionlagrangiana”，Ph.DDisertation，DepartamentodeTecnologaElectronica，UniversidaddeMalaga，Spain，1998.[18] 库恩，H.，和A. Tucker，“非线性规划”，在第二届伯克利数学统计和概率研讨会上，J.Neyman（Ed.），北京：北京大学出版社.加州伯克利，[19] Luemberger D. ， “Introduction to Linear and Non-linear Programming”， 第 二 版 ， Addison-Wesley，Reading，Mass.，一九八四年[20] 拉斯顿湖，[21] 莫里斯湖，MATLAB实验室MPI工具箱（MPITB），URL：http://www.tech.plym.ac.uk/spmc/links/matlab/matlab_mpi.html[22] Octave，URL：http://www.www.gnu.org/software/octave/[23] Ohishi，T.，E. Santos，A.阿尔斯湾Kadowaki，M. Cicogna和S. Soares，2006年6月，俄罗斯圣彼得堡[24] PelicanHPC GNU Linux，URL：http://idea.uab.es/mcreel/ParallelKnoppix/[25] RuggieroM.， 诉 L'opez，“C 'alculo Nu m'erico，As pectos T e' oricos y Computacionales”，MacGr a w-Hill，1988.[26] Shapiro，J.，[27] Stoer，J.，非线性规划中的对偶与极大极小定理，数值数学，5（1963），371 -379.[28] 辛吉雷苏河“Engineering Optimization, Theory and Practice”, Fourth Edition, John Wiley and