換熱網(wǎng)絡(luò)合成問題的并行BB/SQP混合算法

姜楠，劉永忠,2，朱天鴻

?

換熱網(wǎng)絡(luò)合成問題的并行BB/SQP混合算法

姜楠1，劉永忠1,2，朱天鴻1

（1西安交通大學(xué)化學(xué)工程與技術(shù)學(xué)院，陜西西安 710049；2熱流科學(xué)與工程教育部重點(diǎn)實(shí)驗(yàn)室，陜西西安 710049）

換熱網(wǎng)絡(luò)合成問題通常可用非凸、非線性、不可微的混合整數(shù)非線性規(guī)劃模型描述。基于GPU的并行計(jì)算技術(shù)為求解大規(guī)模模型提供了高效支撐。針對已有并行SQP算法求解換熱網(wǎng)絡(luò)合成問題中存在二元變量組合數(shù)過多、并行SQP算法求解結(jié)果嚴(yán)重依賴初值等問題，提出了BB/SQP混合并行算法。該算法采用BB算法代替枚舉法，不但大大減少了模型求解中可能的二元變量組合，而且為SQP算法選出了可行的初值，從而提高了算法的求解質(zhì)量。研究表明，所提出的混合并行算法能夠有效求解換熱網(wǎng)絡(luò)合成問題，且并行計(jì)算相比串行計(jì)算的求解速度顯著增加，加速比可達(dá)39。

換熱網(wǎng)絡(luò)合成；混合整數(shù)非線性規(guī)劃；GPU；并行算法

引 言

為了獲得最小公用工程費(fèi)用、最少換熱單元數(shù)、最小換熱面積和總投資費(fèi)用的換熱網(wǎng)絡(luò)[1-4]，其問題可抽象為復(fù)雜的混合整數(shù)非線性規(guī)劃（MINLP）模型[5-6]。該模型具有非線性和非凸性的特點(diǎn)。采用啟發(fā)式算法難以得到全局最優(yōu)解，而確定性算法的求解時(shí)間過長。因此，目前的趨勢是通過并行加速策略來求解大規(guī)模優(yōu)化模型。目前所采用的主要方法為：直接使用易于并行化的啟發(fā)式算法對模型進(jìn)行求解；或通過模型分割的方法將原問題拆解為可并行求解的一系列子問題，之后對子問題采取并行化處理。

在使用并行的啟發(fā)式算法時(shí)，由于圖形處理器（GPU）表現(xiàn)出優(yōu)越的并行計(jì)算性能，被引入到通用計(jì)算的領(lǐng)域中。一些學(xué)者提出了基于GPU并行加速的粒子群算法求解多目標(biāo)優(yōu)化問題[7-10]，提高了問題的求解效率和算法的尋優(yōu)概率。Wong[11]實(shí)現(xiàn)了基于GPU的并行遺傳算法，且提出了一種基于GPU的多目標(biāo)進(jìn)化算法。Munawar等[12]基于GPU使用改進(jìn)的遺傳算法求解MINLP問題，使用熵測量的方法調(diào)整基因搜索的方向，達(dá)到了雙精度下20和單精度下40的加速比?？蝶愊嫉萚13]提出了一個(gè)基于OpenMP系統(tǒng)的并行遺傳算法，在基本遺傳算法的基礎(chǔ)上引入了一系列調(diào)節(jié)和控制策略，用于改善算法的收斂性，提高了算法獲得最優(yōu)解的概率。然而，上述并行求解優(yōu)化問題的算法僅限于進(jìn)化類算法，這是由進(jìn)化類算法天然并行的特點(diǎn)決定的，并未克服進(jìn)化類算法易于陷入局部最優(yōu)和易于發(fā)散的缺陷。

采用模型分割方法實(shí)現(xiàn)并行化，首先需要將MINLP問題拆解成眾多可并行求解的子問題，主要途徑是通過分解模型中的約束條件來達(dá)到目的。針對較大規(guī)模的MINLP問題，Wah等[14]提出了約束分割法，通過將模型中的約束按一定規(guī)則分割，從而得到一定數(shù)量的子問題，之后即可對子問題進(jìn)行并行求解。Bogataj等[15]提出了一種通過將非凸MINLP問題轉(zhuǎn)化為求解一類單凸MINLP問題的方法，并證明了該方法在模型規(guī)模較小時(shí)能夠保證全局最優(yōu)解。Bjorkqvist等[16]提出了基于Internet的分布式并行求解方法，其目的還是需要整合更多的計(jì)算資源來輔助并行解決MINLP問題中存在的大量計(jì)算密集型任務(wù)。由于GPU更擅長處理計(jì)算密集型任務(wù)，當(dāng)問題規(guī)模不大或者算法處理的任務(wù)數(shù)目或迭代的次數(shù)較少時(shí)，GPU并不能顯著提升計(jì)算性能。而隨著問題規(guī)模的增大，處理數(shù)據(jù)迭代規(guī)模增大時(shí)，GPU的加速效果越發(fā)明顯。

目前對使用確定性算法求解換熱網(wǎng)絡(luò)MINLP問題的研究相對較少，針對確定性算法求解大規(guī)模MINLP問題所需時(shí)間過長甚至無法在有限時(shí)間內(nèi)求解的問題，康麗霞等[17]提出了基于GPU加速求解MINLP問題的SQP并行算法，采用CPU/GPU異構(gòu)并行的策略，以枚舉的方式保證了整數(shù)變量解空間的完備性，構(gòu)建了異步并行的內(nèi)核函數(shù)實(shí)現(xiàn)了NLP子問題的求解。然而，該算法占用內(nèi)存空間較大，且初值依賴性強(qiáng)。

針對啟發(fā)式算法求解質(zhì)量差、確定性算法求解時(shí)間長等問題，通過分析分支定界算法（BB）的可并行性和序貫二次規(guī)劃算法（SQP）求解約束優(yōu)化問題的全局收斂性及其超線性的收斂速度，本文提出了基于GPU加速求解換熱網(wǎng)絡(luò)合成問題的BB/SQP混合并行算法，目標(biāo)是提高求解精度、加快計(jì)算速度。本文將分別介紹串行和并行的BB/SQP混合算法的設(shè)計(jì)，然后采用串行和并行算法分別對換熱網(wǎng)絡(luò)優(yōu)化問題進(jìn)行求解，通過對比，闡明本文算法的準(zhǔn)確性和求解效率。

1 BB與SQP混合算法流程

分支定界算法（BB）是一種求解純整數(shù)或混合整數(shù)規(guī)劃的有效算法，主要通過分支、定界、比較與剪枝3個(gè)關(guān)鍵的步驟進(jìn)行尋優(yōu)，通常其計(jì)算量大大少于窮舉法。序貫二次規(guī)劃算法（SQP）是求解有約束的非線性規(guī)劃問題（NLP）的有效算法之一，是一種循環(huán)迭代算法，具有良好的全局收斂性和超線性的收斂速度。

換熱網(wǎng)絡(luò)合成問題可描述為

模型中包含連續(xù)型變量和二元變量兩類變量。換熱量或流股溫度等參數(shù)用連續(xù)型變量表示，是否存在換熱單元用二元變量表示。

根據(jù)分支定界法的思想，構(gòu)造原問題的松弛問題0，表示為

求解該松弛問題的結(jié)果可分為3種情況：

（1）該松弛問題無解，則原問題也無解，計(jì)算結(jié)束；

（2）該松弛問題有解，且最優(yōu)解滿足原問題的約束，則得到了原問題的最優(yōu)解，計(jì)算結(jié)束；

（3）該松弛問題有解，但最優(yōu)解不滿足原問題的約束，則需要進(jìn)行下一步的分支。

求解1和2子問題，如果1得到了滿足原問題約束的可行解，則將其作為當(dāng)前得到的最優(yōu)解，其相應(yīng)的目標(biāo)函數(shù)值1作為當(dāng)前的上界。接著對結(jié)點(diǎn)2進(jìn)行檢查，如果其有解，再分為3種情況：

（1）若2的解不滿足原問題的約束，且2不小于當(dāng)前的上界，則將2剪枝，1的解即為所求解；

（2）若2的解滿足原問題的約束，且2小于當(dāng)前的上界，則2的解即為所求的全局最優(yōu)解；

（3）若2的解不滿足原問題的約束，且2小于當(dāng)前的上界，則其仍有望得到最優(yōu)解，以2作為父結(jié)點(diǎn)繼續(xù)進(jìn)行分支。

對于第3種情況，選取2的解中某一不滿足整數(shù)約束的解，重復(fù)分支步驟。如此不斷重復(fù)上述的分支、定界和剪枝的過程，如果出現(xiàn)更好的上界，則隨時(shí)更新上界為更小的目標(biāo)函數(shù)值。

對換熱網(wǎng)絡(luò)合成問題的混合整數(shù)非線性規(guī)劃（MINLP）模型，本文將其分解為一系列的混合整數(shù)規(guī)劃（MIP）和非線性規(guī)劃（NLP）子問題，其中的MIP問題可以使用BB算法對混合整數(shù)組合進(jìn)行有選擇的取舍，選取其中有可能通往最優(yōu)解的結(jié)點(diǎn)進(jìn)行分支，同時(shí)每一個(gè)結(jié)點(diǎn)都是一個(gè)NLP問題，可以使用SQP算法對NLP問題進(jìn)行有效的求解。如此一來，可以設(shè)計(jì)出一個(gè)主子結(jié)構(gòu)，主結(jié)構(gòu)使用BB算法作為框架，子結(jié)構(gòu)使用SQP算法求解每個(gè)結(jié)點(diǎn)中的NLP子問題，隨著BB算法的進(jìn)行，分支、定界、剪枝的程度愈加深入，不斷增加的約束條件使NLP問題逐漸滿足原MINLP問題的約束，在遍歷了所有的活結(jié)點(diǎn)后，最終可求得原MINLP問題的最優(yōu)解。

2 串行和并行BB/SQP混合算法設(shè)計(jì)

2.1 串行BB/SQP混合算法的設(shè)計(jì)

本文所需解決問題的目標(biāo)是最小化換熱網(wǎng)絡(luò)的年度費(fèi)用，采取優(yōu)先隊(duì)列式分支定界法。將各結(jié)點(diǎn)按照優(yōu)先級進(jìn)行排序，目標(biāo)函數(shù)值越小的結(jié)點(diǎn)優(yōu)先級越高。因此，本文以最小堆的形式組織活結(jié)點(diǎn)表，將活結(jié)點(diǎn)按照各自的目標(biāo)函數(shù)值排序。如此可以保證每次取出的表首結(jié)點(diǎn)都是活結(jié)點(diǎn)表中目標(biāo)函數(shù)值最小的結(jié)點(diǎn)，結(jié)點(diǎn)一旦被取出后則從活結(jié)點(diǎn)表中刪除。

按照優(yōu)先隊(duì)列式分支定界法的原則，混合算法的流程如圖1所示。

圖1 串行BB/SQP混合算法流程

由圖1可以看出，串行BB/SQP混合算法的基本流程如下。

（1）構(gòu)造換熱網(wǎng)絡(luò)優(yōu)化MINLP問題的松弛問題，記為NLP0。

（2）調(diào)用SQP算法模塊求解NLP0，結(jié)果分為3種情況：若NLP0無解，則原MINLP問題無解，計(jì)算結(jié)束；若NLP0有解且解滿足原MINLP問題的所有約束，則得到原問題的最優(yōu)解，其目標(biāo)函數(shù)值即為最優(yōu)目標(biāo)函數(shù)值，計(jì)算結(jié)束；若NLP0有解但解不滿足原問題的約束條件，則轉(zhuǎn)步驟（3）。

（3）將該結(jié)點(diǎn)加入活結(jié)點(diǎn)表。

（4）若活結(jié)點(diǎn)表不為空，取出活結(jié)點(diǎn)表中的優(yōu)先級最高的結(jié)點(diǎn)，將其分支產(chǎn)生兩個(gè)子問題NLP1和NLP2，之后將該結(jié)點(diǎn)從活結(jié)點(diǎn)表中刪除，調(diào)用SQP求解模塊對子問題分別求解。

（5）對NLP1和NLP2的求解結(jié)果分別進(jìn)行檢查，若其目標(biāo)函數(shù)值大于當(dāng)前的上界，將該結(jié)點(diǎn)舍棄；否則，轉(zhuǎn)步驟（6）。

（6）進(jìn)一步判斷子問題的解是否滿足原問題的約束，若不滿足，轉(zhuǎn)步驟（3）；若滿足，則得到原問題的一組可行解，將其記錄下來，同時(shí)得到一個(gè)更優(yōu)的上界，將上界更新為該結(jié)點(diǎn)的目標(biāo)函數(shù)值，轉(zhuǎn)步驟（4）。

（7）重復(fù)步驟（3）～步驟（6），直到活結(jié)點(diǎn)表為空時(shí)，計(jì)算終止。

在分支步驟中，新產(chǎn)生的子結(jié)點(diǎn)復(fù)制其父結(jié)點(diǎn)的最優(yōu)解作為子結(jié)點(diǎn)中SQP算法的迭代初值。相比一般的初值，從父結(jié)點(diǎn)繼承的最優(yōu)解通常情況下能夠更接近子結(jié)點(diǎn)的最優(yōu)解，為SQP算法提供更好的初值，加速問題的求解。

2.2 并行BB/SQP混合算法的設(shè)計(jì)

由于并行化程序的要求，需要將算法設(shè)計(jì)為若干適于并行獨(dú)立求解的部分，因此如何將任務(wù)進(jìn)行合理分解是本算法的重點(diǎn)。

分支定界算法的搜索起始于一個(gè)根結(jié)點(diǎn)，這一根結(jié)點(diǎn)是將原混合整數(shù)規(guī)劃中整數(shù)約束的部分去掉，將整數(shù)變量松弛為連續(xù)型變量進(jìn)行求解的，其解空間會(huì)相應(yīng)增大。通常情況下，根結(jié)點(diǎn)的解難以滿足原問題的約束，但是其目標(biāo)函數(shù)值可作為該優(yōu)化問題最優(yōu)解的一個(gè)下界，可先通過并行SQP算法對根結(jié)點(diǎn)求解，如果根結(jié)點(diǎn)的解不是原問題的解，則將原問題分解為若干子問題，再利用并行混合算法進(jìn)行求解。

在換熱網(wǎng)絡(luò)合成問題的MINLP模型中，其中的二元變量數(shù)目為已知，假設(shè)為，則個(gè)二元變量的所有組合形式即為完整的換熱網(wǎng)絡(luò)結(jié)構(gòu)序列，可通過窮舉得到，其總數(shù)為2，或者可以看做是深度為1的滿二叉樹的所有葉子結(jié)點(diǎn)所構(gòu)成的集合，如圖2所示。

圖2中，結(jié)點(diǎn)內(nèi)的序列表示已確定的二元變量組合即部分網(wǎng)絡(luò)結(jié)構(gòu)。可以看出，深度不同，結(jié)點(diǎn)數(shù)目不同，結(jié)點(diǎn)的深度與其已確定的不完整的結(jié)構(gòu)序列位數(shù)一一對應(yīng)，且左子結(jié)點(diǎn)是在其父結(jié)點(diǎn)結(jié)構(gòu)序列的基礎(chǔ)上增加一位，以“0”占位；右子結(jié)點(diǎn)是在其父結(jié)點(diǎn)結(jié)構(gòu)序列的基礎(chǔ)上增加一位，以“1”占位，即下層的結(jié)點(diǎn)均是由上層的結(jié)點(diǎn)分支得到，且不會(huì)有遺漏。這與需要獲得某一位的組合序列的思路是一致的。為了利用GPU并行計(jì)算的特性，可根據(jù)問題的規(guī)模，選取分支樹的某一深度，列舉出深度為時(shí)的所有結(jié)點(diǎn)的組合序列共2-1種，它們是最終網(wǎng)絡(luò)結(jié)構(gòu)的前-1位的所有組合形式。將這些結(jié)點(diǎn)加入初始活結(jié)點(diǎn)表中，之后分別初始化于每個(gè)block中作為并行深度優(yōu)先分支定界法搜索的根結(jié)點(diǎn)，深度的選取需要同時(shí)考慮所要求解問題的整型變量數(shù)目以及硬件自身的能力。

圖2 分支樹的深度與產(chǎn)生組合數(shù)目的關(guān)系

經(jīng)并行初始化之后，每個(gè)block擁有各自預(yù)先確定的部分網(wǎng)絡(luò)結(jié)構(gòu)。因此，每個(gè)block都可看作是一個(gè)深度優(yōu)先分支定界法的根結(jié)點(diǎn)，可通過核函數(shù)（kernel）執(zhí)行并行的深度優(yōu)先搜索（DFS）[18]，如圖3所示。

圖3 根結(jié)點(diǎn)與block的關(guān)系

圖3中，初始活結(jié)點(diǎn)表中的每個(gè)結(jié)點(diǎn)均作為深度優(yōu)先搜索的根結(jié)點(diǎn)，同時(shí)分布于各個(gè)block中，之后以其為根結(jié)點(diǎn)的深度優(yōu)先搜索DFS在每個(gè)block中執(zhí)行，除了搜索方式不同，其他執(zhí)行過程與串行混合算法相似，如此每一個(gè)子空間都可以同時(shí)進(jìn)行求解，且每個(gè)block中的解均為原問題解空間中的子集。這里所執(zhí)行的深度優(yōu)先搜索是一個(gè)回溯的過程，其本質(zhì)是先序遍歷一棵狀態(tài)樹，同時(shí)將狀態(tài)樹的建立隱含在遍歷過程中，使用它可以避免窮舉式搜索，這種方式適用于求解一些組合數(shù)相當(dāng)大的問題[19]。本文所設(shè)計(jì)的結(jié)合并行SQP算法的深度優(yōu)先BB/SQP搜索流程如圖4所示。

從圖4可以看出，在執(zhí)行分支時(shí)每次只產(chǎn)生一個(gè)子結(jié)點(diǎn)，子結(jié)點(diǎn)的迭代初值可設(shè)置為其父結(jié)點(diǎn)的最優(yōu)解，如果該子結(jié)點(diǎn)經(jīng)過比較之后被剪枝，則將搜索返回其父結(jié)點(diǎn)，分支產(chǎn)生另一子結(jié)點(diǎn)。

圖4 深度優(yōu)先搜索算法流程

下面給出本文所采用的深度優(yōu)先BB/SQP搜索的基本步驟：

（1）設(shè)置各根結(jié)點(diǎn)的初始信息，包括對初始結(jié)構(gòu)序列和變量賦初值，讀入已知數(shù)據(jù)等；

（2）選取其中某一分支進(jìn)行試探，即在缺省的網(wǎng)絡(luò)結(jié)構(gòu)序列中添加一位“0”或“1”；

（3）使用并行SQP算法對該結(jié)點(diǎn)進(jìn)行求解，之后判斷此分支是否可行，若不可行則轉(zhuǎn)步驟（6）；

（4）若分支可行則前進(jìn)一步繼續(xù)試探；

（5）找到一組可行解則進(jìn)行記錄，若未找到則轉(zhuǎn)步驟（2）；

（6）選取另一分支進(jìn)行搜索，轉(zhuǎn)步驟（3），若該結(jié)點(diǎn)的分支全部試探完則轉(zhuǎn)步驟（7）；

（7）退回一步返回父結(jié)點(diǎn)，若未退到頭則轉(zhuǎn)步驟（6）；

（8）已退到頭則結(jié)束或輸出無解。

當(dāng)所有block完成搜索之后，會(huì)產(chǎn)生大量的解，此時(shí)需要執(zhí)行同步步驟來確保所有block均已計(jì)算完畢，并且將所有block的解匯總比較，進(jìn)行最優(yōu)解的篩選。

由于DFS的過程發(fā)生在device端，而GPU的流處理器相對簡單，若在device端使用復(fù)雜的分支與定界程序會(huì)大大影響GPU的執(zhí)行效率。因此，本文通過使用有序的分支策略和一個(gè)簡單的定界函數(shù)來替代串行部分復(fù)雜的分支定界過程，以此緩解GPU的這一局限。線程間的同步和問題的規(guī)模是影響程序執(zhí)行時(shí)間的兩個(gè)重要因素，因此應(yīng)該設(shè)置更緊的上界以剪掉更多的分支，創(chuàng)建更小的分支定界樹，避免上界的多次更新同步。因此初始上界的設(shè)置就顯得尤為重要，通?？赏ㄟ^啟發(fā)式算法或多項(xiàng)式近似的方法來得到相對合適的初始上界。如果問題的規(guī)模很大，所需求解的并行的子問題過多時(shí)，可按子問題數(shù)目選擇合適的block數(shù)目，通過多輪實(shí)現(xiàn)的形式，每輪計(jì)算一部分子問題，將問題分批次處理。圖5給出了并行混合算法的計(jì)算流程。

圖5 并行BB/SQP混合算法流程

3 算例分析

本文算例計(jì)算所用設(shè)備為一臺(tái)安裝了Nvidia Tesla K20c和Quadro K600的工作站，計(jì)算環(huán)境為：CPU為Pentium(R) Dual-Core CPU E5800，3.20 GHz。軟件環(huán)境為：Windows 7操作系統(tǒng)，CUDA toolkit版本為6.0。

GPU為Nvidia Tesla K20c顯卡一塊，流處理器內(nèi)核數(shù)量104，CUDA核心數(shù)量2496，計(jì)算能力3.5，單精度浮點(diǎn)性能3.52 Tflop·s-1，容量4 GB，時(shí)鐘頻率0.71 GHz；Quadro K600顯卡一塊，流處理器內(nèi)核數(shù)量8，CUDA核心數(shù)量192，計(jì)算能力3.0，單精度浮點(diǎn)性能194.84 Gflop·s-1，顯存容量1 GB，時(shí)鐘頻率0.88 GHz。

3.1 對小型換熱網(wǎng)絡(luò)模型的計(jì)算測試

本節(jié)采用一個(gè)規(guī)模較小的換熱網(wǎng)絡(luò)案例來進(jìn)行測試，算例來源于文獻(xiàn)[20]。該換熱網(wǎng)絡(luò)包括2股熱流和2股冷流，基礎(chǔ)數(shù)據(jù)如表1所示。

表1 算例1的流股數(shù)據(jù)

本例換熱網(wǎng)絡(luò)模型規(guī)模為2×2×3，無分流，最小傳熱溫差為10 K，模型中共包含68個(gè)變量，其中有16個(gè)整型變量。采用本文算法得到的換熱網(wǎng)絡(luò)結(jié)構(gòu)見圖6。表2中列出了串行程序與并行程序計(jì)算結(jié)果的對比，并與文獻(xiàn)中的結(jié)果進(jìn)行比較。

由表可見，串行計(jì)算和并行計(jì)算均得到了比文獻(xiàn)中更優(yōu)的目標(biāo)函數(shù)值，表明本文算法能夠很好地求解小型換熱網(wǎng)絡(luò)優(yōu)化問題，且并行程序相比串行程序執(zhí)行時(shí)間大大縮短，達(dá)到了約39的加速比。

圖6 算例1的換熱網(wǎng)絡(luò)結(jié)構(gòu)

表2 算例1的計(jì)算結(jié)果對比

3.2 對中型換熱網(wǎng)絡(luò)模型的計(jì)算測試

本節(jié)將對一個(gè)規(guī)模較大換熱網(wǎng)絡(luò)的MINLP模型進(jìn)行測試，該算例來源于文獻(xiàn)[21]，基礎(chǔ)數(shù)據(jù)見表3。

表3 算例2的流股數(shù)據(jù)

本算例的規(guī)模為4×3×2，有分流，最小傳熱溫差為1 K，模型中共有整型變量31個(gè)，連續(xù)變量95個(gè)。由于串行程序的計(jì)算時(shí)間過長，本節(jié)僅給出采用并行計(jì)算進(jìn)行測試的結(jié)果，所得到的換熱網(wǎng)絡(luò)結(jié)構(gòu)如圖7所示，結(jié)果對比如表4所示。

由表可見，本文設(shè)計(jì)的并行混合算法可求得算例2的最優(yōu)整型變量組合，其相應(yīng)的目標(biāo)函數(shù)值不僅優(yōu)于文獻(xiàn)中的最優(yōu)目標(biāo)函數(shù)值，且得到了切實(shí)可行的換熱網(wǎng)絡(luò)設(shè)計(jì)方案，證明了本文設(shè)計(jì)算法可以對換熱網(wǎng)絡(luò)的MINLP問題進(jìn)行有效求解。

圖7 算例2的換熱網(wǎng)絡(luò)結(jié)構(gòu)

4 結(jié) 論

針對換熱網(wǎng)絡(luò)的合成問題，本文分析并設(shè)計(jì)了將分支定界算法與序貫二次規(guī)劃算法相結(jié)合的混合算法，同時(shí)實(shí)現(xiàn)了混合算法的串行計(jì)算和基于GPU的并行計(jì)算。通過對兩個(gè)規(guī)模不同的算例進(jìn)行測試，驗(yàn)證了本文提出的BB/SQP并行混合算法對于求解換熱網(wǎng)絡(luò)優(yōu)化問題的有效性。對比串行計(jì)算和并行計(jì)算，本文提出的并行混合算法具有顯著的加速效果。

[1] BAKAR S H A, HAMID M K A, ALWI S R W. Selection of minimum temperature difference (Δmin) for heat exchanger network synthesis based on trade-off plot [J]. Applied Energy, 2016, 162 (15): 1259-1271.

[2] NOVAK P Z, KRAVANJA Z. A methodology for the synthesis of heat exchanger networks having large numbers of uncertain parameters [J]. Energy, 2015, 92 (3): 373-382.

[3] GROSSMANN I E, APAP R M, CALFA B A. Recent advances in mathematical programming techniques for the optimization of process systems under uncertainty [J]. Computers & Chemical Engineering, 2015, 37 (1): 1-4.

[4] LEE S, GROSSMANN I E. A global optimization algorithm for nonconvex generalized disjunctive programming and applications to process systems [J]. Computers & Chemical Engineering, 2001, 25 (11): 1675-1697.

[5] YEE T F, GROSSMANN I E, KRAVANJA Z. Simultaneous optimization models for heat integration (Ⅰ): Area and energy targeting and modeling of multi-stream exchangers [J]. Computers & Chemical Engineering, 1990, 14 (10): 1151-1164.

[6] YEE T F, GROSSMANN I E. Simultaneous optimization models for heat integration (Ⅱ): Heat exchanger network synthesis [J]. Computers & Chemical Engineering, 1990, 14 (10): 1165-1184.

[7] ZHOU Y, TAN Y. GPU-based parallel multi-objective particle swarm optimization [J]. International Journal of Artificial Intelligence, 2011, 7 (11): 125-141.

[8] WANG J, WU Z. Opposition-based particle swarm optimization for solving large scale optimization problems on GPU [J]. Journal of Wuhan University(Natural Science), 2011, 57 (2): 148-154.

[9] MUSSI L, DAOLIO F, CAGNONI S. Evaluation of parallel particle swarm optimization algorithms within the CUDA architecture [J]. Information Sciences, 2011, 181 (20): 4642-4657.

[10] MUSSI L, NASHED Y S G, CAGNONI S. GPU-based asynchronous particle swarm optimization [C]//Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. Dublin: ACM. 2011: 1555-1562.

[11] WONG M L. Parallel multi-objective evolutionary algorithms on graphics processing units [C]//Proceedings of the Conference on Genetic and Evolutionary Computation. Canada: Companion Material, 2009: 2515-2522.

[12] MUNAWAR A, WAHIB M, MUNETOMO M. Advanced genetic algorithm to solve MINLP problems over GPU [C]//Congress of Evolutionary Computation. LA: IEEE, 2011: 318-325.

[13] 康麗霞, 姜楠, 夏明星, 等. 基于OpenMP的并行GA加速求解換熱網(wǎng)絡(luò)設(shè)計(jì) [J]. 高校化學(xué)工程學(xué)報(bào), 2016, 30 (2): 423-438. KANG L X , JIANG N, XIA M X,Paralleled genetic algorithm for design of HEN based on OpenMP system [J]. Journal of Chemical Engineering of Chinese Universities, 2016, 30 (2): 423-438.

[14] WAH B W, CHEN Y X. Constraint partitioning in penalty formulations for solving temporal planning problems [J]. Artificial Intelligence, 2006, 170 (3): 187-231.

[15] BOGATAJ M, KRAVANJA Z. An alternative strategy for global optimization of heat exchanger networks [J]. Applied Thermal Engineering, 2012, 43 (43): 75-90.

[16] BJORKQVIST J, WESTERLUND T. Parallel solution of disjunctive MINLP problems [J]. Chemical Engineering Communications, 2002, 185 (1): 115-124.

[17] 康麗霞, 張燕蓉, 唐亞哲, 等.基于GPU加速求解MINLP問題的SQP并行算法 [J]. 化工學(xué)報(bào), 2012, 63 (11): 3597-3601. KANG L X, ZHANG Y R, TANG Y Z,. Paralleled SQP algorithm for solution of MINLP problems based on GPU acceleration [J].CIESC Journal, 2012, 63 (11): 3597-3601.

[18] CHAKROUN I, MELAB N. Operator-level GPU-accelerated branch and bound algorithms [J]. Procedia Computer Science, 2013, 18 (1): 280-289.

[19] CARNEIRO T, MURITIBA A E, NEGREIROS M. A new parallel schema for branch-and-bound algorithms using GPGPU [C]//Computer Architecture and High Performance Computing. Espirito Santo: IEEE, 2011: 41-47.

[20] ZAMORA J M, GROSSMANN I E. A global MINLP optimization algorithm for the synthesis of heat exchanger networks with no stream splits [J]. Computers & Chemical Engineering, 1998, 22 (3): 367-384.

[21] VIDYASHANKAR K, NARASIMHAN S. Comparison of heat exchanger network synthesis using Floudas and Yee superstructures [J]. Indian Chemical Engineer, 2010, 52 (1): 1-22.

Parallel algorithm of hybrid BB/SQP for heat exchanger network synthesis

JIANG Nan1, LIU Yongzhong1,2, ZHU Tianhong1

(1School of Chemical Engineering and Technology, Xi’an Jiaotong University, Xi’an 710049, Shaanxi, China; 2Key Laboratory of Thermo-Fluid Science and Engineering, Ministry of Education, Xi’an 710049, Shaanxi, China)

Heat exchanger network synthesis can be described by a mixed integer non-linear programming (MINLP) model, which features non-convex, non-linear and non-differentiable optimization. The parallel computing technology based on GPU provides an efficient support for solving large scale models. In this work, a hybrid algorithm combined branch and bound method (BB) with sequential quadratic programming (SQP) is proposed to overcome difficulties in the existing parallel SQP algorithm, such as too many combinations of integer variables, dependency of initial values and. The BB method is adopted in the hybrid algorithm instead of the exhaustive method. It can not only reduce the combinations of integer variables, but also select feasible initial values for the SQP algorithm. The solution quality is improved. The results of the examples show that the proposed parallel hybrid algorithm can solve the heat exchanger network synthesis problems efficiently. Compared to the serial algorithm, the proposed parallel algorithm has much higher executive speed with the speedup ratio of 39.

heat exchanger network synthesis; mixed integer non-linear programming; GPU; hybrid algorithm

date: 2016-09-13.

Prof. LIU Yongzhong, yzliu@mail.xjtu.edu.cn

10.11949/j.issn.0438-1157.20161287

TQ 021.8

A

0438—1157（2016）12—5169—07

國家自然科學(xué)基金項(xiàng)目（21376188，21676211）。

supported by the National Natural Science Foundation of China (21376188, 21676211).

2016-09-13收到初稿，2016-09-22收到修改稿。

聯(lián)系人：劉永忠。第一作者：姜楠（1990—），男，碩士研究生。