一種基于拉格朗日與時(shí)間解耦的超大規(guī)模SCUC求解框架

彭超逸，顧慧杰，周華鋒，邱方堃，張淼，葛言

（1.中國(guó)南方電網(wǎng)電力調(diào)度控制中心，廣州 510663；2.杉數(shù)科技（北京）有限公司，北京 100102；3.上海財(cái)經(jīng)大學(xué)交叉科學(xué)研究院，上海 200433）

0 引言

隨著電力市場(chǎng)改革逐漸進(jìn)入深水區(qū)，特別是“雙碳”目標(biāo)的提出以及電力需求增速不斷提高，在市場(chǎng)環(huán)境下電力供應(yīng)系統(tǒng)的穩(wěn)定、有效和安全運(yùn)行變得越來(lái)越重要。安全約束機(jī)組組合（security constrained unit commitment，SCUC）是電力市場(chǎng)中最基本的優(yōu)化問(wèn)題之一，旨在滿足電力系統(tǒng)安全性約束的條件下，制定多時(shí)段的機(jī)組開停機(jī)計(jì)劃。2021 年，全國(guó)全社會(huì)用電量8.31 TWh，其中火電占比超過(guò)50%，燃煤機(jī)組啟動(dòng)過(guò)程的復(fù)雜性對(duì)于機(jī)組啟停的決策優(yōu)化提出了很高的要求。

SCUC 可以被建模為一個(gè)混合整數(shù)線性規(guī)劃問(wèn)題（mixed-integer linear programming，MILP），由于它是NP-hard 問(wèn)題，很難找到高效快速的算法。一般而言，SCUC 問(wèn)題的求解會(huì)在商業(yè)求解器中進(jìn)行，但是對(duì)于超大規(guī)模的SCUC 問(wèn)題，由于其具有大量的變量和跨期約束，直接調(diào)用求解器無(wú)法在合理時(shí)間內(nèi)得到可行解，從而無(wú)法保障電力系統(tǒng)實(shí)時(shí)調(diào)度的準(zhǔn)備時(shí)間，影響電力系統(tǒng)的正常運(yùn)行。因此如何基于求解器設(shè)計(jì)一套泛用、高效的求解算法框架成為了目前研究的重要方向。其中混合整數(shù)規(guī)劃、拉格朗日松弛法與分解算法是解決SCUC 問(wèn)題的常用方法。

在混合整數(shù)規(guī)劃相關(guān)方法中，國(guó)內(nèi)外的研究基本圍繞著減小問(wèn)題規(guī)模的角度去設(shè)計(jì)相應(yīng)的算法，嘗試構(gòu)造更加簡(jiǎn)潔緊湊的模型。在文獻(xiàn)［1］中，作者提出了一種快速安全約束機(jī)組組合（fast security constrained unit commitment，F(xiàn)-SCUC）方法。該方法的核心思想是減少混合整數(shù)規(guī)劃中整數(shù)變量的數(shù)量，通過(guò)在求解初期固定單元的狀態(tài)，削減問(wèn)題的規(guī)模，若固定狀態(tài)后的模型無(wú)解，則逐步將固定的狀態(tài)調(diào)整成變量，納入模型進(jìn)行求解，該方法能有效提升計(jì)算效率，但準(zhǔn)確性欠佳。文獻(xiàn)［2］嘗試通過(guò)引入輔助優(yōu)化問(wèn)題，建立安全約束失效的具體條件，識(shí)別無(wú)效的安全約束，從而減小SCUC 問(wèn)題的規(guī)模、提高求解效率。文獻(xiàn)［3］將凸包理論從單機(jī)組場(chǎng)景拓展到多機(jī)組場(chǎng)景，利用線性規(guī)劃來(lái)近似混合整數(shù)規(guī)劃問(wèn)題，提高了大規(guī)模電力系統(tǒng)組合模型的求解效率。文獻(xiàn)［4］將機(jī)組系統(tǒng)建立成0-1變量的混合整數(shù)二次規(guī)劃問(wèn)題，采用啟發(fā)式算法減少目標(biāo)機(jī)組數(shù)目，縮小優(yōu)化空間，并將處理后的模型利用有效集割平面算法進(jìn)行求解。文獻(xiàn)［5］建立了一種包含4 類0-1 變量的機(jī)組組合混合整數(shù)規(guī)劃模型，提出了簡(jiǎn)潔的啟動(dòng)費(fèi)用線性公式與機(jī)組出力約束公式，縮小了最優(yōu)解的搜尋空間，有效提高了求解效率。但是一般而言混合整數(shù)規(guī)劃在求解大規(guī)模SCUC 問(wèn)題時(shí)往往不能在較短的時(shí)間內(nèi)得到有效的解，需要借助其他方法進(jìn)一步降低問(wèn)題的難度。

本文采用的拉格朗日松弛方法也是一種有效的方法，其基本原理是將對(duì)問(wèn)題求解造成困難的約束吸收到目標(biāo)函數(shù)中，得到相對(duì)容易解決的拉格朗日松弛問(wèn)題［6］。它的最優(yōu)值為原問(wèn)題最優(yōu)值的提供了一個(gè)界，其質(zhì)量將會(huì)部分依賴于吸收到目標(biāo)函數(shù)中所選取的參數(shù)。拉格朗日松弛方法于1970 年被文獻(xiàn)［7］提出，其應(yīng)用范圍包括了十幾種最困難的組合優(yōu)化問(wèn)題，使解決大規(guī)模問(wèn)題成為可能。文獻(xiàn)［8］和文獻(xiàn)［9］分別提出了基于拉格朗日松弛方法的快速算法對(duì)機(jī)組組合問(wèn)題與電網(wǎng)布點(diǎn)及容量規(guī)劃問(wèn)題進(jìn)行求解。

雖然線性的拉格朗日松弛方法能夠以迭代的形式避開復(fù)雜約束加速求解，但是在大規(guī)模的復(fù)雜問(wèn)題中傳統(tǒng)的拉格朗日松弛方法會(huì)存在收斂困難的情況，特別是在最優(yōu)解附近會(huì)存在震蕩現(xiàn)象。為了解決這一問(wèn)題，文獻(xiàn)［10］在1995 年提出了在拉格朗日松弛問(wèn)題的目標(biāo)函數(shù)中引入二次項(xiàng)。由于序列二次 規(guī) 劃 問(wèn) 題（sequential quadratic programming，SQP）在求解時(shí)收斂性更強(qiáng)，因此該方法成功解決了傳統(tǒng)拉格朗日方法長(zhǎng)時(shí)間不收斂的問(wèn)題。雖然拉格朗日松弛方法可以解決難解約束以及收斂性問(wèn)題，但是由于問(wèn)題規(guī)模過(guò)于巨大，仍需進(jìn)一步使用分解算法來(lái)縮小問(wèn)題規(guī)模。

現(xiàn)有的SCUC 分解算法大都是基于地理位置以及應(yīng)用場(chǎng)景進(jìn)行分割。文獻(xiàn)［11］利用漸進(jìn)對(duì)沖算法（progressive hedging algorithm，PHA）將問(wèn)題按照不同場(chǎng)景進(jìn)行分割求解。文獻(xiàn)［12］開發(fā)了一套協(xié)同并發(fā)搜索技術(shù)和基于場(chǎng)景的分解技術(shù)，分別用于計(jì)算確定性情況與隨機(jī)情況下的每小時(shí)日前機(jī)組組合（hourly day-ahead unit commitment）。文獻(xiàn)［13］利用基于場(chǎng)景的分解算法來(lái)解決兩階段隨機(jī)機(jī)組組合問(wèn)題。文獻(xiàn)［14］利用Benders 分解將SCUC 問(wèn)題分解成了一個(gè)主問(wèn)題和若干子問(wèn)題并將應(yīng)急約束考慮在內(nèi)。文獻(xiàn)［15-17］按照地理位置將SCUC 問(wèn)題分解成若干子問(wèn)題，并使用并行算法來(lái)協(xié)調(diào)各個(gè)子問(wèn)題。文獻(xiàn)［18］總結(jié)了電力系統(tǒng)分區(qū)與解耦相關(guān)的研究，基于地理位置與拓?fù)浣Y(jié)構(gòu)對(duì)各類分區(qū)準(zhǔn)則進(jìn)行了匯總與評(píng)述，并指出當(dāng)前較優(yōu)的方法為快速解耦與相序解耦。文獻(xiàn)［19］運(yùn)用基于多目標(biāo)差分進(jìn)化算法（multi-objective evolutionary algorithm based on decomposition，MOEA/D）和多目標(biāo)蟻群優(yōu)化算法，將優(yōu)化問(wèn)題分解為多個(gè)子問(wèn)題分別進(jìn)行蟻群算法求解，動(dòng)態(tài)生成分區(qū)方案，并使用二代非支配排序遺傳算法（non-dominated sorting genetic algorithmⅡ，NSGA-Ⅱ）求解最優(yōu)解集。文獻(xiàn)［20］將配電網(wǎng)按照饋線規(guī)模進(jìn)行劃分，作為獨(dú)立的求解模塊進(jìn)行分區(qū)處理，并基于ZeroMQ 技術(shù)構(gòu)建了分布式并行計(jì)算框架，在配電網(wǎng)節(jié)點(diǎn)超過(guò)500 個(gè)時(shí)具有明顯速度優(yōu)勢(shì)。

上述文獻(xiàn)從不同的角度將原問(wèn)題分解成多個(gè)子問(wèn)題，但是實(shí)際應(yīng)用的SCUC 問(wèn)題無(wú)論地理位置或者是饋線規(guī)模等都存在著巨大的耦合性，無(wú)法輕易進(jìn)行分解。相對(duì)來(lái)說(shuō)，從時(shí)間角度出發(fā)進(jìn)行約束解耦是更優(yōu)的方法。實(shí)際上時(shí)間解耦方法已經(jīng)被廣泛應(yīng)用于電網(wǎng)動(dòng)態(tài)無(wú)功優(yōu)化［21］、風(fēng)電機(jī)組-機(jī)械動(dòng)態(tài)優(yōu)化［22］等領(lǐng)域，但極少數(shù)文獻(xiàn)考慮SCUC 場(chǎng)景下的時(shí)間解耦算法［23-24］。文獻(xiàn)［25］利用拉格朗日松弛方法，通過(guò)將爬坡約束和最小啟停時(shí)間約束等時(shí)間耦合約束放松，將原問(wèn)題分解成若干子問(wèn)題求解，并使用分支定界法尋找原問(wèn)題的最優(yōu)解。文獻(xiàn)［26］考慮了潮流約束和網(wǎng)絡(luò)安全約束，將問(wèn)題分解為一個(gè)主問(wèn)題與若干時(shí)段的子問(wèn)題，分別處理機(jī)組的啟停、出力與可行性校驗(yàn)，利用Benders算法進(jìn)行協(xié)調(diào)。

最近有一些學(xué)者嘗試將機(jī)器學(xué)習(xí)與魯棒優(yōu)化中的方法引入機(jī)組組合問(wèn)題中。文獻(xiàn)［27］從機(jī)組組合問(wèn)題中的負(fù)荷曲線特征出發(fā)，將負(fù)荷水平聚類為有限個(gè)狀態(tài)，建立了關(guān)于負(fù)荷狀態(tài)轉(zhuǎn)移的模型，從而有效削減了問(wèn)題規(guī)模，提高了在中長(zhǎng)期機(jī)組組合場(chǎng)景下的求解效率。文獻(xiàn)［28］基于K-means 算法與長(zhǎng)短期記憶（long short-term memory，LSTM）深度學(xué)習(xí)模型，試圖利用歷史數(shù)據(jù)刻畫決策與系統(tǒng)負(fù)荷之間的關(guān)系，提高模型的適用性與求解效率。文獻(xiàn)［29］基于魯棒優(yōu)化提出了嵌套式列生成的雙層分解循環(huán)算法用于求解N-k故障約束的機(jī)組組合問(wèn)題。文獻(xiàn)［30］提出了一種多目標(biāo)驅(qū)動(dòng)的動(dòng)態(tài)規(guī)劃算法，能夠?qū)崿F(xiàn)跨時(shí)間的高效滾動(dòng)規(guī)劃，用于求解天然氣與電力混合機(jī)組問(wèn)題。文獻(xiàn)［31］基于改進(jìn)的Kmeans 算法，對(duì)運(yùn)行初始場(chǎng)景進(jìn)行縮減，并構(gòu)建了兩階段機(jī)組啟停模型。

現(xiàn)有的方法大多存在兩個(gè)問(wèn)題：一是很多文獻(xiàn)使用了經(jīng)典數(shù)據(jù)集作為標(biāo)準(zhǔn)，傳統(tǒng)經(jīng)典數(shù)據(jù)集的規(guī)模較小，而實(shí)際生產(chǎn)環(huán)境中的求解規(guī)模要比標(biāo)準(zhǔn)數(shù)據(jù)集大將近8～10 倍，對(duì)于混合整數(shù)規(guī)劃（mixedinteger programming，MIP）這種極度困難的NPhard 問(wèn)題來(lái)說(shuō)，標(biāo)準(zhǔn)數(shù)據(jù)集上的求解結(jié)果并不能夠滿足實(shí)際求解需求；二是在關(guān)注到時(shí)間解耦算法的文獻(xiàn)中，大部分都引入了一些二次項(xiàng)懲罰以連接各個(gè)子問(wèn)題模塊，而這種二次項(xiàng)在超大規(guī)模的MIP中是不可接受的。

本文提出了一個(gè)線性化的解耦框架，并使用改進(jìn)的拉格朗日松弛方法進(jìn)一步加速SCUC 問(wèn)題求解。線性化的時(shí)間解耦框架主要可以根據(jù)時(shí)間維度將問(wèn)題分為多個(gè)子問(wèn)題依次求解，減少求解時(shí)間；而改進(jìn)的拉格朗日松弛方法能夠處理稠密耦合性強(qiáng)的復(fù)雜約束，提升整體求解效率和保證一定的最優(yōu)性。下文將詳細(xì)介紹SCUC 模型、改進(jìn)拉格朗日松弛方法和線性化的時(shí)間解耦框架，并通過(guò)數(shù)值實(shí)驗(yàn)來(lái)說(shuō)明算法的有效性。

1 模型介紹

本文針對(duì)區(qū)域電力市場(chǎng)日前出清模型展開了研究，日前電力市場(chǎng)與實(shí)際運(yùn)行情況較為接近，其出清結(jié)果對(duì)市場(chǎng)交易和系統(tǒng)運(yùn)行均具有重要意義［32］。本文在參考文獻(xiàn)［33-35］的基礎(chǔ)上建立了模型，由于日前出清市場(chǎng)目前實(shí)際場(chǎng)景下使用的是每日96個(gè)決策區(qū)間，因此求解的決策顆粒度為15 min。在日前市場(chǎng)的出清中出清目標(biāo)最優(yōu)與求解效率提升均為算法考慮的范疇。

1.1 變量

本文涉及到的變量類型如表1所示。

表1 變量描述Tab.1 Variables description

1.2 目標(biāo)函數(shù)

目標(biāo)函數(shù)為電網(wǎng)總體運(yùn)行成本的最小化，電網(wǎng)的運(yùn)行成本包括發(fā)電成本、棄水成本和違反斷面約束懲罰具體如下。

發(fā)電成本FP和棄水成本FW的計(jì)算如下。

機(jī)組發(fā)電量與單價(jià)的關(guān)系如圖1所示。

圖1 機(jī)組發(fā)電量與單價(jià)關(guān)系示意圖Fig.1 Schematic diagram of the relationship between generating capacity and unit price

1.3 約束

本文的SCUC 模型大部分采取了較為經(jīng)典的建模方式［33-35］，主要涉及的約束如下所示。

1.3.1 備用約束

備用約束指的是某個(gè)省開機(jī)的機(jī)組要比當(dāng)前該省發(fā)電機(jī)總出力留有一定量的向上和向下調(diào)節(jié)能力。

1.3.2 機(jī)組與聯(lián)絡(luò)線組爬坡約束

對(duì)于火力發(fā)電的機(jī)組，機(jī)組發(fā)電功率在上/下爬坡時(shí)，均應(yīng)當(dāng)滿足其爬坡速率要求。對(duì)于聯(lián)絡(luò)線組，其在某個(gè)時(shí)間點(diǎn)出力需要受到相鄰時(shí)間點(diǎn)的出力值的影響。與機(jī)組爬坡不同的是聯(lián)絡(luò)線組爬坡需要考慮最小爬坡與最大爬坡，下爬坡和上爬坡都是同一個(gè)值，即需要引入向上爬坡和向下爬坡的兩類變量。

1.3.3 機(jī)組與聯(lián)絡(luò)線出力約束

機(jī)組開機(jī)時(shí)有出力的下限和上限，關(guān)機(jī)時(shí)出力為0，在某些時(shí)間指定為關(guān)機(jī)狀態(tài)并且不發(fā)電；水電機(jī)組需要考慮振動(dòng)區(qū)，即出力區(qū)間是分段的。對(duì)于聯(lián)絡(luò)線，若某時(shí)間點(diǎn)不存在于拓?fù)渲?，則出力上界和下界均為0；若屬于自由變化方向的類型，則上下界需要體現(xiàn)出方向（正負(fù)）的信息。

式中：Dk，t為電氣島嶼k在時(shí)間t的電量負(fù)荷；Ik為電氣島嶼k中的機(jī)組集合；Jsrc為送端聯(lián)絡(luò)線集合；Jdst為受端聯(lián)絡(luò)線集合。某個(gè)電氣島嶼中所有的發(fā)電機(jī)的出力總和-該電氣島嶼輸送出去的電量+該電氣島嶼接受到的電量=該電氣島嶼的電量負(fù)荷。

1.3.5 機(jī)組開關(guān)機(jī)決策

式中：I為機(jī)組集合；Noni和Noffi分別為機(jī)組i所允許的最大、最小開機(jī)次數(shù)；Tu，i為機(jī)組i的最小持續(xù)開機(jī)時(shí)間；Td，i為機(jī)組i的最小持續(xù)關(guān)機(jī)時(shí)間；Igas為燃?xì)鈾C(jī)組集合；Nig為燃?xì)鈾C(jī)組ig中包含的機(jī)組數(shù)量。機(jī)組狀態(tài)與決策相容（僅在關(guān)機(jī)狀態(tài)下才能做開機(jī)決策，反之亦然），機(jī)組單日啟停次數(shù)、最小連續(xù)啟停時(shí)間限制在給定范圍內(nèi)，處于相同燃?xì)鈾C(jī)組群的燃?xì)鈾C(jī)組保持同啟同停。

1.3.6 水電相關(guān)約束

下述幾條約束為稠密和復(fù)雜的安全約束。

1.3.7 斷面潮流約束

斷面約束為電網(wǎng)中一個(gè)重要的安全約束的類型之一，其是否越限以及越限的程度都將嚴(yán)重影響電網(wǎng)運(yùn)行安全的穩(wěn)定。

1.3.8 線路輸電約束

線路輸電約束為電網(wǎng)中一個(gè)重要的安全約束的類型之一，其是否越限以及越限的程度都將嚴(yán)重影響電網(wǎng)運(yùn)行安全的穩(wěn)定。

1.3.9 交流聯(lián)絡(luò)線潮流約束

本文考慮多個(gè)區(qū)域的SCUC 問(wèn)題。由于區(qū)域外的聯(lián)絡(luò)線傳輸功率一般由各區(qū)域間事先協(xié)商確定，這里提及的交直流聯(lián)絡(luò)線約束主要指的是區(qū)域內(nèi)交直流聯(lián)絡(luò)線約束。交流聯(lián)絡(luò)線原本是非線性建模，為了讓交流聯(lián)絡(luò)線參與建模，我們將其線性化和近似化表示。

交流聯(lián)絡(luò)線潮流安全約束是指在任意時(shí)間點(diǎn)，交流聯(lián)絡(luò)線擁有拓?fù)浣Y(jié)構(gòu)，不能像直流聯(lián)絡(luò)線一樣進(jìn)行自由優(yōu)化，需要受到拓?fù)浣Y(jié)構(gòu)中的機(jī)組、直流聯(lián)絡(luò)線和負(fù)荷的影響。

在日常實(shí)際求解中，需要在求解完畢后校驗(yàn)斷面、交流聯(lián)絡(luò)線潮流約束，如果存在違反，則相應(yīng)調(diào)整上下限重新求解。本文更加關(guān)注SCUC 的MIP形式本身求解，調(diào)整約束上下界對(duì)于求解問(wèn)題本身難度變化幾乎為零，因此在本文中不作詳細(xì)介紹。

斷面潮流和交流聯(lián)絡(luò)線潮流這兩類約束對(duì)于求解器存在著巨大的求解困難。求解器開發(fā)者曾經(jīng)提出一個(gè)觀點(diǎn)，在構(gòu)建模型時(shí)要盡可能地避免構(gòu)造出稠密的系數(shù)矩陣，一般以20 個(gè)非零元左右為界。而上述的兩條約束對(duì)大規(guī)模電網(wǎng)而言，集合了幾乎所有與電網(wǎng)相關(guān)的設(shè)備，遠(yuǎn)遠(yuǎn)高于20個(gè)非零元。在實(shí)際求解中我們也發(fā)現(xiàn)，正是因?yàn)檫@兩種約束，大大增加了問(wèn)題求解的難度。因此針對(duì)這種情況，本文提出了一種基于拉格朗日迭代的SCUC算法框架。

2 算法介紹

2.1 時(shí)間解耦算法

2.1.1 算法框架

盡管地理區(qū)域、不確定性場(chǎng)景和應(yīng)急場(chǎng)景的分解可能會(huì)減少SCUC 的計(jì)算時(shí)間，但它們無(wú)法處理源自時(shí)間約束的計(jì)算復(fù)雜性。這種復(fù)雜性隨著調(diào)度間隔數(shù)量的增加而增加?？紤]調(diào)度間隔之間的偶然性和相互依賴性會(huì)增加SCUC 的計(jì)算時(shí)間。因此在考慮的調(diào)度時(shí)間范圍內(nèi)分解SCUC 可能是比地理分解更有前途的策略。

時(shí)間解耦的方法在工業(yè)界實(shí)踐中已經(jīng)被證明為最為有效的分解思路之一，在諸多不同工業(yè)場(chǎng)景下諸如工業(yè)排產(chǎn)，列車排班等等場(chǎng)景中往往可以提高近百倍的求解效率，同時(shí)最優(yōu)求解的gap 可以有效確保在0.1%左右，完全能夠符合日常排產(chǎn)的精度要求。上述SCUC模型可以表示為如下形式。

式中：I、P、T分別為機(jī)組開關(guān)、發(fā)電出力、傳輸功率的變量；Dscuc為問(wèn)題的可行域。本文將總體的時(shí) 間 區(qū) 間T={1，2，…，n} 分 為k段Ti={ti-1，…，ti- 1}，i= 1，…，k，其 中，1 =t0≤t1≤…≤tk=n+ 1。考慮如下分割：

式中：Ii、Pi、Ti分別為屬于分段Ti的開關(guān)機(jī)組、發(fā)電出力、傳輸功率的變量；Di為只含有Ti中變量的約束集合；Doverlap為存在跨越時(shí)間段約束的集合。

我們考慮按照給定順序T1，T2，…，Tk求解下列子問(wèn)題。

對(duì)于Optj，j

時(shí)間解耦算法遵循以下幾個(gè)步驟。

1） 根據(jù)上面所定義的問(wèn)題，構(gòu)造出Ti對(duì)應(yīng)的子問(wèn)題，同時(shí)初始化隊(duì)列；

2） 首先求解處于隊(duì)列第一的T1對(duì)應(yīng)的子問(wèn)題，由于不存在其余的Optj，j

3） 根據(jù)解出的Optj，j

4） 將得到的解進(jìn)行拼裝即可得到嚴(yán)格可行的I、P、T。

時(shí)間解耦求解框架如圖2所示。

圖2 時(shí)間解耦求解框架Fig.2 Framework of time decoupling solution

Doverlap中主要包含以下兩類約束，分別具體處理如下。

1） 機(jī)組開關(guān)機(jī)決策

在該類約束中，都存在著機(jī)組開關(guān)機(jī)決策變量I跨越時(shí)間分段的情況，因此在求解問(wèn)題Opti時(shí)，需要固定Ij，j= 1，…，i- 1 這些變量，這些變量先于Opti已經(jīng)解出。在求解完Opti后下一個(gè)問(wèn)題中需要進(jìn)一步固定Ij，j= 1，…，i求解Opti+1。

2） 機(jī)組與聯(lián)絡(luò)線組爬坡約束

在該類約束中，跨越時(shí)間分段的主要有兩種變量：發(fā)電出力變量P和傳輸功率變量TLG。處理方法同1）。

2.1.2 全局最優(yōu)性約束

在實(shí)際算例求解中，由于約束之間耦合性較強(qiáng)，框架中直接對(duì)子問(wèn)題進(jìn)行分別求解可能會(huì)過(guò)分忽視子問(wèn)題之間的關(guān)聯(lián)性，造成框架求解最優(yōu)性被嚴(yán)重破壞。因此，需要在解耦框架之上增加一種全局性的提示。

考慮一個(gè)原問(wèn)題的近似問(wèn)題如式（21）所示。

式中D′scuc的形成遵從以下幾個(gè)規(guī)則。

1） 所有的整數(shù)變量松弛為連續(xù)變量；

2） 第1節(jié)中除斷面潮流約束和交流聯(lián)絡(luò)線潮流約束外，其余的約束不作改動(dòng)；

3） 在斷面潮流約束以及交流聯(lián)絡(luò)線潮流約束中采樣部分約束，除保留指定關(guān)鍵斷面以外，其他約束采用隨機(jī)抽取的方式。

這種隨機(jī)抽取的方式并不會(huì)影響求解全局問(wèn)題，其重要原因在于容易違反的斷面約束幾乎完全集中在關(guān)鍵斷面之中，這些關(guān)鍵斷面是結(jié)合日常生產(chǎn)經(jīng)驗(yàn)以及一些啟發(fā)式算法共同得出的，實(shí)踐中這種隨機(jī)抽取并不會(huì)引起過(guò)多的其他約束的違反。同時(shí)，在計(jì)算效率上，后續(xù)的拉格朗日框架中由于所有斷面約束均統(tǒng)一加入了懲罰，問(wèn)題形式不會(huì)有太大的變化，并不會(huì)引起求解效率的降低。

由此，問(wèn)題的求解難度顯著地下降。原因如下：1）整數(shù)變量被松弛，使原問(wèn)題成為了線性規(guī)劃問(wèn)題；2）難以求解的斷面以及交流線約束數(shù)量減少。但與此同時(shí)，問(wèn)題的求解并沒(méi)有損失太大的最優(yōu)性。由式（21）得到的解(I′，P′，T′)添加一個(gè)全局性的正則項(xiàng)懲罰，構(gòu)造以下問(wèn)題。

式中λglobal為全局懲罰參數(shù)。本文通過(guò)構(gòu)造1-模懲罰的方式將全局最優(yōu)性納入了框架考慮中，注意到這種懲罰函數(shù)的形式仍然為線性的，只是目標(biāo)函數(shù)的形式發(fā)生了變化，因此時(shí)間解耦框架依然適用，且更接近最優(yōu)解。

2.2 針對(duì)網(wǎng)絡(luò)安全約束的拉格朗日松弛迭代

經(jīng)過(guò)上述算法迭代后子問(wèn)題雖然已經(jīng)大幅度降低了規(guī)模，但是求解仍然會(huì)存在困難，這是由于子問(wèn)題本身存在著難以求解的約束?？紤]導(dǎo)致子問(wèn)題求解困難的兩類約束：斷面潮流約束以及交流聯(lián)絡(luò)線潮流約束。

基于拉格朗日松弛迭代的SCUC 模型的算法具體流程如下。

1） 定位出SCUC 模型中稠密的耦合性約束，如SCUC 模型中的斷面潮流約束和交流聯(lián)絡(luò)線約束，初始化對(duì)偶拉格朗日乘子， 跳至2）。

2） 根據(jù)拉格朗日松弛的原理，將以上耦合約束通過(guò)拉格朗日乘子加入到目標(biāo)函數(shù)中，生成拉格朗日對(duì)偶問(wèn)題，第ν次迭代中具體形式如下所示（以斷面潮流約束為例）。

5） 判斷式（23）迭代是否達(dá)到收斂（Oν+1-Oν≤σ），若達(dá)到收斂條件，則跳至6）；若未達(dá)到收斂條件，則跳至3）。

6） 在SCUC 模型求解中使用拉格朗日迭代為子問(wèn)題帶來(lái)了重要的改進(jìn)，這是由于去除了這兩類極為稠密的約束后，原問(wèn)題的稀疏性得到了極大的恢復(fù)。同時(shí)添加在原問(wèn)題的目標(biāo)函數(shù)上的懲罰項(xiàng)并不會(huì)過(guò)度地影響問(wèn)題的數(shù)值穩(wěn)定性，因?yàn)楸疚臅?huì)通過(guò)δ控制懲罰項(xiàng)的量級(jí)，以確保原問(wèn)題的最優(yōu)性不會(huì)被破壞。

由于潮流約束越限數(shù)量決定了電網(wǎng)日常運(yùn)行的穩(wěn)定性程度，因此在問(wèn)題（23）的迭代結(jié)束后若仍有部分?jǐn)嗝嬖较?，則還需要將這些越限的斷面通過(guò)松弛懲罰的形式加入到SCUC 模型的目標(biāo)函數(shù)中，并將第ν個(gè)問(wèn)題（23）求解后未越限的斷面以硬約束的形式加入到模型中，求解MILP 問(wèn)題，跳至7）。MILP問(wèn)題具體如下所示。

以上兩部分算法使得原始超大規(guī)模的問(wèn)題線性化的拆解成為了多個(gè)子問(wèn)題，與此同時(shí)，針對(duì)稠密困難的約束，設(shè)計(jì)了一種線性化的松弛方案。與傳統(tǒng)拉格朗日迭代不同的是，這種松弛方案多考慮了一步由線性松弛問(wèn)題到原問(wèn)題的一個(gè)近似MILP 的轉(zhuǎn)換，以企圖在不損失大量精度的情況下快速求解這個(gè)超大規(guī)模的SCUC 問(wèn)題。下一章數(shù)值實(shí)驗(yàn)將闡明該求解框架的有效性。

3 數(shù)值實(shí)驗(yàn)

3.1 數(shù)據(jù)介紹

本文選取了我國(guó)實(shí)際的某區(qū)域日前電力市場(chǎng)場(chǎng)景連續(xù)7 d 的真實(shí)算例，算例統(tǒng)一分為2 個(gè)分島。圖3 為分島之間需要的輸電量。圖4 展示了整個(gè)電網(wǎng)系統(tǒng)每日總負(fù)荷情況，可以看出隨著負(fù)荷上升分島之間輸電量一般呈正比關(guān)系。

圖3 分島之間輸電量Fig.3 Power transmission between islands

圖4 電網(wǎng)負(fù)荷Fig.4 Power grid load

表2 展示了電網(wǎng)部分運(yùn)行參數(shù)。可以看到，電網(wǎng)存在一部分常量，如機(jī)組的數(shù)量。同時(shí)算例之間也有不同，如斷面的數(shù)量。

表2 電網(wǎng)部分參數(shù)Tab.2 Partial parameters of power grid

綜上，可以看到，目前本文所需要求解的具體問(wèn)題規(guī)模龐大，難度極高，一般標(biāo)準(zhǔn)數(shù)據(jù)集難以企及。

3.2 參數(shù)設(shè)置及計(jì)算結(jié)果分析

我們采用python 語(yǔ)言編寫程序，在CPU 型號(hào)為64 核，Intel（R） Xeon（R） Platinum 8 356 H CPU@3.90 GHz，內(nèi)存為256 G 的設(shè)備上進(jìn)行了實(shí)驗(yàn)。本文將根據(jù)發(fā)電成本、斷面越限量以及計(jì)算時(shí)間來(lái)衡量算法的穩(wěn)定性。在分解算法方面，本文分別比較了分段數(shù)為1（不分段）和2（分為兩段）的求解效果，而對(duì)于拉格朗日迭代，本文則比較了使用前后的計(jì)算效率。各算法參數(shù)系數(shù)設(shè)置如表3所示。

表3 參數(shù)設(shè)置Tab.3 Parameters setting

3.2.1 求解效率對(duì)比

實(shí)驗(yàn)共展示7 個(gè)實(shí)時(shí)日前算例求解效率，這7個(gè)日前出清問(wèn)題的問(wèn)題規(guī)模如表4所示。

表4 問(wèn)題規(guī)模比較Tab.4 Comparison of problem sizes

以上7 個(gè)算例都屬于百萬(wàn)級(jí)別的數(shù)學(xué)規(guī)劃問(wèn)題，對(duì)于商業(yè)求解器而言，這已經(jīng)屬于較難求解的范疇，因此單純求解問(wèn)題本身已經(jīng)非常困難，加上數(shù)值問(wèn)題，導(dǎo)致了直接使用求解器幾乎不可能完成這樣的數(shù)學(xué)規(guī)劃求解。因此另外單獨(dú)使用了拉格朗日迭代算法以及分解算法進(jìn)行求解，求解效率結(jié)果如表5所示。

表5 算法求解效率比較Tab.5 Comparison of algorithm solving efficiencies s

由表5 可見(jiàn)使用了分解算法后子問(wèn)題的求解仍然會(huì)存在困難，而拉格朗日迭代算法由于巧妙地規(guī)避了求解器可能遇到的數(shù)值問(wèn)題，求解迅速，在原始不能求解的問(wèn)題上獲得了巨大的效率提升。拉格朗日迭代算法加入了分解算法之后，問(wèn)題的求解變得更為穩(wěn)定，且用時(shí)更短。最好的情況下，在部分拉格朗日迭代問(wèn)題上獲得了近3 倍的提速，如算例5 由于輸入?yún)?shù)的原因，導(dǎo)致求解器構(gòu)建的問(wèn)題數(shù)值情況不佳，但是分解算法由于縮減了子問(wèn)題求解規(guī)模因此很好的抵消了數(shù)值問(wèn)題帶來(lái)的影響。

3.2.2 求解結(jié)果對(duì)比

本文還比較了兩者最優(yōu)性的情況，通過(guò)比較兩者目標(biāo)函數(shù)值的差異來(lái)證明算法的有效性，具體結(jié)果如表6所示。

表6 目標(biāo)函數(shù)值比較Tab.6 Comparison of objective function values

由表6 可見(jiàn)兩種算法求解結(jié)果相近，在算例4與7 中，分解算法甚至獲得了比拉格朗日迭代更好的目標(biāo)函數(shù)結(jié)果，這是由于λglobal的統(tǒng)一設(shè)置以及拉格朗日迭代本身帶來(lái)的最優(yōu)性損失使得算法并沒(méi)有收斂到全局最優(yōu)點(diǎn)，而分解算法在此時(shí)則有可能更為接近全劇最優(yōu)解。

在此必須要指出SCUC 問(wèn)題目標(biāo)函數(shù)的近似下界也是很難給出的。兩者給出的上界結(jié)果相近，實(shí)踐中可以認(rèn)為兩種算法都已經(jīng)得到了接近全局意義上的上確界，這也證實(shí)了算法的有效性。同時(shí)由于直接求解無(wú)法在合理時(shí)間內(nèi)得到最優(yōu)解，而分解算法兩段直接求解也與其他可算算法的目標(biāo)函數(shù)值比較接近，在一定程度上接近最優(yōu)解。

3.2.3 數(shù)值實(shí)驗(yàn)總結(jié)

表7 給出了兩種算法的表現(xiàn)，數(shù)值實(shí)驗(yàn)證明，兩種算法的結(jié)合能夠更加快速地求解超大規(guī)模SCUC出清問(wèn)題，且求解更為穩(wěn)定。

表7 算法表現(xiàn)比較Tab.7 Algorithms performance comparison

4 結(jié)語(yǔ)

一般而言實(shí)際場(chǎng)景中的超大規(guī)模SCUC 出清問(wèn)題直接使用求解器進(jìn)行求解非常困難，因此本文從求解器求解難點(diǎn)出發(fā)提出了兩種算法：1）以降低求解規(guī)模為目的的時(shí)間解耦算法；2）一種能夠降低模型稠密度的拉格朗日松弛算法。同時(shí)，針對(duì)這類超大規(guī)模問(wèn)題構(gòu)建了基于這兩種算法的求解框架。

數(shù)值實(shí)驗(yàn)證明，基于時(shí)間解耦以及拉格朗日迭代的算法在不損失較大精度的情況下獲得了極大加速，滿足了實(shí)際業(yè)務(wù)需求，為區(qū)域電力現(xiàn)貨市場(chǎng)提供了有力的技術(shù)支持。

未來(lái)還可以開展更進(jìn)一步的工作：一方面，實(shí)驗(yàn)發(fā)現(xiàn)，盡管大部分情況下分為多段求解會(huì)獲得更高的效率，但是少數(shù)情況求解會(huì)出現(xiàn)不穩(wěn)定的情況，因此如何確定優(yōu)化分段也可以作為一大研究方向；另一方面，盡管得到的解已經(jīng)較優(yōu)，分解算法的最優(yōu)性仍然存在優(yōu)化空間，如果能夠考慮分段之間求解的交互，而非完全獨(dú)立，那么最優(yōu)性可以獲得進(jìn)一步提升。