武 昱，黃思明

(1.中國科學(xué)院科技戰(zhàn)略咨詢研究院，北京 100190；2.中國科學(xué)院大學(xué)，北京 100049)

超大規(guī)模線性規(guī)劃的稀疏存儲和預(yù)處理中比例行的檢測和處理方法

武 昱1,2，黃思明1

(1.中國科學(xué)院科技戰(zhàn)略咨詢研究院，北京 100190；2.中國科學(xué)院大學(xué)，北京 100049)

隨著大數(shù)據(jù)時代的到來，線性規(guī)劃問題的規(guī)模越來越大是一種必然。面對超大規(guī)模線性規(guī)劃問題，如何存儲數(shù)據(jù)，使得存儲空間節(jié)省以避免資源的浪費，并且使得數(shù)據(jù)的查詢、修改和增刪方便快捷，是一個急需解決的問題。本文提出了基于十字鏈表的數(shù)據(jù)稀疏存儲方式。并且，通過對Netlib數(shù)據(jù)庫中的超大規(guī)模線性規(guī)劃問題進(jìn)行存儲分析，對此種存儲方式的優(yōu)越性進(jìn)行了驗證。此外，由于大量冗余數(shù)據(jù)的存在，在應(yīng)用算法求解超大規(guī)模線性規(guī)劃問題之前，往往需要進(jìn)行預(yù)處理，而比例行的檢測和處理是預(yù)處理中必要的關(guān)鍵一步，因此本文提出了比例行的檢測和處理方法。首先給出了不同于常理的比例行及其他相關(guān)概念的定義；然后結(jié)合本文提出的數(shù)據(jù)存儲方式，提出了簡單易操作的比例行檢測方法；接著總結(jié)已有文獻(xiàn)得出了比例行消除操作的兩個基本原則，并在此基礎(chǔ)上通過對比例行所含有的非零元素進(jìn)行分類，通過理論分析推導(dǎo)出了保證約束矩陣稀疏度不降且單獨列增加的比例行處理方法。最后，首先通過一個微型算例對比例行檢測和處理的具體過程進(jìn)行了演示和分析，然后通過Netlib數(shù)據(jù)庫中的6個實際線性規(guī)劃問題，對比例行檢測和處理方法真正作用于超大規(guī)模線性規(guī)劃問題時的效果進(jìn)行了驗證。

線性規(guī)劃；預(yù)處理；十字鏈表；稀疏存儲；比例行

1 引言

隨著大數(shù)據(jù)時代的到來，大規(guī)模問題的研究已經(jīng)成為一個熱點。近年來，許多學(xué)者在不同領(lǐng)域都已開展了大規(guī)模問題的研究工作，如藍(lán)伯雄和王童姝[1]對大規(guī)?？瓦\專線運營的研究、許啟發(fā)等人[2]對指令不均衡與股票收益關(guān)系的研究、 李暉等人[3]對大規(guī)模農(nóng)產(chǎn)品生產(chǎn)計劃的研究、阮俊虎等人[4]對大規(guī)模災(zāi)害的研究和陳驥等人[5]對大規(guī)模群體評價的研究。大規(guī)模問題研究的興起，一方面是由于隨著數(shù)據(jù)規(guī)模的擴(kuò)大，傳統(tǒng)的適用于小規(guī)模問題的模型或方法不再適用；另一方面是由于大規(guī)模問題會產(chǎn)生一些新問題，比如數(shù)據(jù)的存儲問題和處理效率問題。

在線性規(guī)劃研究領(lǐng)域，同樣面領(lǐng)著數(shù)據(jù)規(guī)模越來越大的挑戰(zhàn)。隨著科技和經(jīng)濟(jì)的發(fā)展，尤其是隨著大數(shù)據(jù)時代的到來，線性規(guī)劃問題的規(guī)模越來越大，含有成千上萬個約束和變量的線性規(guī)劃問題已非常常見[6-8]。面對這些超大規(guī)模的線性規(guī)劃問題，如何存儲數(shù)據(jù)、如何在應(yīng)用具體算法求解之前通過預(yù)處理消除冗余，從而節(jié)省存儲空間、提高求解效率，是一個急需解決的問題。

目前，大規(guī)模線性規(guī)劃問題通常用內(nèi)點算法求解，而內(nèi)點算法不允許約束矩陣中出現(xiàn)相關(guān)行。然而，大規(guī)模問題一般都是由模型支持工具自動生成的，往往存在大量冗余的約束和變量。所以，在應(yīng)用算法求解之前進(jìn)行數(shù)據(jù)預(yù)處理是必要的。而在進(jìn)行數(shù)據(jù)預(yù)處理的過程中，比例行的檢測和處理是必不可少的關(guān)鍵一步[9-11]。

因此，本文以超大規(guī)模線性規(guī)劃問題為研究背景，首先對超大規(guī)模線性規(guī)劃中的比例行給出了更為寬泛的定義，其次描述了改進(jìn)了的十字鏈表的稀疏存儲方式，然后基于具體的數(shù)據(jù)存儲結(jié)構(gòu)，提出了簡單易操作的比例行檢測方法和處理方法，最后，結(jié)合具體的算例，驗證了本文所提出方法的有效性。

2 基本模型及相關(guān)概念的定義

通常的線性規(guī)劃模型如下：

用矩陣形式表示如下：

其中，c=(c1,c2,…,cn),x=(x1,x2,…,xn)T,A=(aij)m×n,b=(b1,b2,…,bm)T。

在以上的線性規(guī)劃模型中，矩陣A被稱為約束矩陣，行向量c被稱為價值系數(shù)向量，列向量b被稱為資源約束向量?；谶@些基本概念，下面給出本文所討論的比例行及其他相關(guān)概念的定義。

在線性規(guī)劃問題的約束矩陣中，如果某列僅含有一個非零元素，則稱該列為單獨列，即如果A的第j列元素滿足：?k:akj≠0,且?i≠k,aij=0,則稱第j列為單獨列。第k行為含有單獨列的行，第k行的第j個元素aik稱為第k行的單獨列元素。Andersen和Andersen[9]在處理比例行時，區(qū)別對待單獨列元素和非單獨列元素，本文采用類似的處理方法定義超大規(guī)模線性規(guī)劃問題中的比例行。比例行及其對比例行進(jìn)行處理時涉及到的其他概念定義如下。

比例行：約束矩陣中的兩行(或者多行)，如果除去各自所含有的單獨列元素，其他元素對應(yīng)成比例，則該兩行構(gòu)成比例行。用數(shù)學(xué)語言表述如下：?i,k:vaij=akj,i≠k,?j?S。其中S是構(gòu)成單獨列的變量的標(biāo)號的集合。

基準(zhǔn)行：在處理構(gòu)成比例關(guān)系的行簇時，作為一次消除操作的基準(zhǔn)，本身不發(fā)生任何變化的行，稱為基準(zhǔn)(本)行。

消除操作：若兩約束行構(gòu)成比例行，依據(jù)比例關(guān)系，從其中一個約束行的兩邊等價地消去與另一行構(gòu)成比例的部分，這一操作稱為消除操作。

3 超大規(guī)模線性規(guī)劃問題數(shù)據(jù)的存儲

超大規(guī)模線性規(guī)劃問題往往是稀疏的，即A,b,c中存在著大量的零元素，如果按照正常的存儲方式進(jìn)行存儲，零元素將占用大量的存儲空間，造成資源的浪費。因此，采用稀疏存儲的方式對超大規(guī)模線性規(guī)劃問題的數(shù)據(jù)進(jìn)行存儲，尤其是對約束矩陣A進(jìn)行存儲，是經(jīng)常使用的辦法。常見的稀疏存儲的方式有三元組存儲和鏈表存儲[12,13]。本文采用改進(jìn)的十字鏈表存儲約束矩陣A。為了形象直觀的表示如何采用改進(jìn)的十字鏈表對約束矩陣A進(jìn)行存儲，本文假設(shè)A是一個5行4列的含有5個非零元素的稀疏矩陣，則對A的存儲如圖1所示。

在圖1中，十字鏈表中的節(jié)點分為元素節(jié)點和表頭節(jié)點兩種類型。元素節(jié)點對矩陣A中的零元素不進(jìn)行存儲，對非零元素用一個含有5個成員變量的結(jié)構(gòu)體(Structure)進(jìn)行存儲。結(jié)構(gòu)體含有的5個成員變量的數(shù)據(jù)類型從左到右、從上到下依次是(int，int，double，*structure, *structure)。前兩個int類型的變量，表示的是非零元素在矩陣A中位置，即非零元素的行標(biāo)值i和列標(biāo)值j；第三個double類型的變量表示的是非零元素本身的值，即A(i,j)的值；最后兩個結(jié)構(gòu)體指針類型的變量，分別表示的是非零元素所在行和所在列的下一個非零元素的存儲地址，如果該非零元素是其所在行(所在列)的最后一個非零元素，則其相應(yīng)的結(jié)構(gòu)體類型的指針變量表示的是該非零元素所在行(所在列)的行(列)表頭節(jié)點的地址。

圖1 基于十字鏈表稀疏存儲的示意圖

表頭節(jié)點同樣是含有5個成員變量的結(jié)構(gòu)體，它們的數(shù)據(jù)類型依次(int, int, *structure, *structure, *structure)。通常進(jìn)行稀疏存儲的十字鏈表中[12]，表頭節(jié)點的前兩個int型的變量中存放默認(rèn)值0，而在本文使用的十字鏈表中，第一個int型變量中存放以該節(jié)點為行表頭節(jié)點的行所含有的非零元素的個數(shù)，第二個int型變量中存放以該節(jié)點為列表頭節(jié)點的列所含有的非零元素的個數(shù)。如果該節(jié)點僅作為行(列)表頭節(jié)點，則其第二個(第一個)int型成員變量中存放無窮大值。例如，在圖1中，矩陣A的第二列含有兩個非零元素，第二行含有一個非零元素，因此，在十字鏈表的第二個行(列)表頭節(jié)點的前兩個int型的變量中存放的數(shù)分別是2和1。并且，這兩個int型變量中存放的非零元素的數(shù)值將隨著矩陣第二行和第二列中非零元素個數(shù)的變化而變化。

改進(jìn)之后的十字鏈表用于存儲超大規(guī)模線性規(guī)劃問題的約束矩陣，將使得存儲空間極大的節(jié)省。為了驗證這一特性，本文從Netlib數(shù)據(jù)庫中選取了約束矩陣的元素個數(shù)超過兩千萬的超大規(guī)模線性規(guī)劃問題進(jìn)行存儲分析，結(jié)果見表1所示。此外，改進(jìn)后的十字鏈表還將使得數(shù)據(jù)的查詢、修改和增刪更為便捷，從而使得線性規(guī)劃預(yù)處理的效率得到了很大的提高，這一特性在本文下一部分比例行的檢測中，將得到驗證。

表1 Netlib數(shù)據(jù)庫中約束矩陣元素個數(shù)大于2×108的線性規(guī)劃問題的存儲分析

4 比例行的檢測

由前面的定義可知，本文所研究的比例行并不是嚴(yán)格意義上構(gòu)成比例的約束行，即包括右側(cè)資源約束向量在內(nèi)，約束行之間僅差一個常數(shù)乘數(shù)因子而構(gòu)成的比例行。本文所研究的比例行，是指除去所包含的構(gòu)成單獨列的元素以及右側(cè)資源約束向量之外，其余各元素成比例的約束行。在這種界定下，嚴(yán)格意義下的比例行只是本文所研究的比例行的一個特例，因此本文所提出的檢測和處理方法自然適用，不再贅述。

文獻(xiàn)[14]中提出的比例行檢測方法，適用于嚴(yán)格意義上構(gòu)成比例的約束行，并不適用于本文所研究的定義更為寬泛的比例行。并且此檢測方法沒有以具體的數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu)為背景，不能直接應(yīng)用于基于十字鏈表存儲的超大規(guī)模線性規(guī)劃問題。因此，本文以Tomlin和Welch[14]中的檢測方法為基礎(chǔ)，提出了適用于包含單獨列元素的、基于十字鏈表存儲的超大規(guī)模線性規(guī)劃問題的比例行檢測方法。下面將描述本文所提出的比例行檢測方法的具體檢測過程，在本文最后，將通過實例來進(jìn)一步說明該檢測方法的可行性和有效性。

假設(shè)(m,n)為約束矩陣的維度，即m為約束矩陣所包含的行約束的數(shù)目，n為約束矩陣所對應(yīng)的線性規(guī)劃問題的決策變量的個數(shù)。r(i,j)表示第i列的第j個非零元素的行標(biāo)值。定義“分類數(shù)組”(Class Array),記為CA[m]。在檢測方法執(zhí)行的過程中，已確定不與任何其他行存在比例關(guān)系的行，置其CA值為-INF。有可能構(gòu)成比例關(guān)系的行，有相同的且不等于-INF的CA值。算法運行結(jié)束后，CA值相同且不為-INF 的行是構(gòu)成比例關(guān)系的行。初始值設(shè)置為CA[j]=0,j=1,2,…,m, 即開始檢測之前，認(rèn)為所有的約束行之間都存在比例關(guān)系。定義“比例因子數(shù)組”(Scalar Array)，記為SA[m]，初始值設(shè)置為：SA[j]=0,j=1,2,…,m。定義布爾“指示數(shù)組”(Indicating Array)記為IA[m],初始值設(shè)置為:IA[j]=false,j=1,2,…,m，SA[j]表示第j行是否已經(jīng)被開始檢測，true表示已經(jīng)被開始檢測，false表示還沒有被開始檢測。定義布爾“階段性指示數(shù)組”(Period Indicating Array)記為PIA[m]，初始值設(shè)置為PIA[j]=false,j=1,2,…m, true表示在檢測第i列的過程中，第j行還沒有被檢測，false表示第j行已經(jīng)被檢測。

該檢測方法的實質(zhì)是一個分類的過程，存在比例關(guān)系的行屬于同一個類。開始檢測前，認(rèn)為所有的行之間都存在比例關(guān)系，即所有的行都屬于同一個類，都有相同的CA值，CA值代表類的編號。從第1列到第n列，逐列開始檢測，隨著檢測的不斷進(jìn)行，類的個數(shù)將不斷增多，設(shè)c為下一個即將出現(xiàn)的新的類的編號。

比例行檢測方法如下：

步驟1：設(shè)置i=0,c=1；

步驟2：i=i+1，令PIA[j]=true,j=1,2,…,m。(在開始檢測新的一列之前，階段性指示數(shù)組復(fù)原)。

(1)如果i<=n，判斷十字鏈表中第i列列表頭節(jié)點的第二個int型變量的值是否為1：

①如果等于1，重復(fù)執(zhí)行步驟2；

②如果大于1，記為ci，執(zhí)行步驟3；

(2)如果i>n,執(zhí)行步驟4；

步驟3：按照十字鏈表的列指針，依次掃描第i列的ci個非零元素：設(shè)置j=1。

(1)如果j<=ci，讀取r(i,j)，

①如果PIA[r(i,j)]=false,j=j+1, 返回(1)

②如果PIA[r(i,j)]=true,讀取IA[r(i,j)]的值：

a)如果IA[r(i,j)=false，尋找該列中IA值同樣為false的其他所有行t(j+1

b)如果IA[r(i,j)]=true，尋找該列中其他IA值為false、PIA值為true、CA值與CA[r(i,j)]相等的所有行t(j+1

(2)如果j>ci,返回步驟2。

步驟4：從1到n, 檢測CA的值， CA值為-INF的行不與其他任何行構(gòu)成比例行，具有相同CA(不等于-INF)值的行相互之間構(gòu)成比例關(guān)系。比例行檢測結(jié)束。

綜上，以上檢測方法進(jìn)行一次從第一列到第n列的檢測操作，就可以找到約束矩陣中所有存在比例關(guān)系的約束行。并且，由于該檢測是在十字鏈表上進(jìn)行的，因而只需檢測約束矩陣中的非零元素，對于僅含有一個元素的單獨列只需檢測其表頭節(jié)點即可。所以，應(yīng)用該比例行檢測方法，能夠極大的提高超大規(guī)模線性規(guī)劃預(yù)處理中比例行的檢測效率。針對該檢測方法的檢測結(jié)果，本文下一部分將分析討論如何對這些構(gòu)成比例關(guān)系的約束行進(jìn)行處理。

5 比例行的處理

上一部分重點敘述了在基于十字鏈表的存儲結(jié)構(gòu)下，比例行的檢測方法。這一部分在已知比例行檢測結(jié)果的基礎(chǔ)上，將討論如何處理這些存在比例關(guān)系的約束行。為了便于后續(xù)對比例行具體的處理操作，首先定義二元列與多元列的概念如下。

二元列(Two-element column)：線性規(guī)劃約束矩陣中，若某列含有兩個非零元素，則稱該列為二元列，數(shù)學(xué)表示如下：

?j,?k1,?k2,?i,ak1j≠0,ak2j≠0,i≠k1且i≠k2,aij=0,則第j列為二元列.多元列(Multi-element column)：線性規(guī)劃約束矩陣中，若某列含有三個或以上非零元素，則稱該列為多元列，數(shù)學(xué)語言表示為：

?j,?k1,k2,…kn,?i,ak1j≠0,ak2j≠0,…aknj≠0;i≠k1∧i≠k2∧…∧i≠kn，aij=0,則第j列為n元列(n≥3)。

對于構(gòu)成比例關(guān)系的約束行，具體如何進(jìn)行處理, 才能使得一方面既消除了冗余的約束，一方面又能保證約束矩陣的稀疏程度，本文首先從已有文獻(xiàn)中歸納出了比例行處理的兩個基本原則，然后從對兩個約束行構(gòu)成比例關(guān)系的處理和對多個(大于等于3)約束行構(gòu)成比例關(guān)系的處理兩方面分別進(jìn)行討論分析。

5.1比例行處理的基本原則

由Anderson和Anderson[9]和Gondzio[10]可知，利用單獨列(自由或隱性free column or implied column)可以把一個變量和一個約束從原問題中移除，而且在約束矩陣中還不會產(chǎn)生額外的非零元素，即既使得線性規(guī)劃問題的規(guī)模變小，又不會影響約束矩陣的稀疏程度。因此，本文在處理比例行時，在不產(chǎn)生額外的非零元素的前提下，采取盡可能的增加單獨列數(shù)目的處理方法，這是本文進(jìn)行比例行處理的第一個處理原則。另一方面，在超大規(guī)模的線性規(guī)劃問題中，約束矩陣往往含有大量的零元素，因此在其求解時若采用稀疏存儲，不僅可以節(jié)省大量的內(nèi)存空間，使得超大規(guī)模的線性規(guī)劃問題在普通個人計算機(jī)上的成功求解成為可能，而且還能使得線性規(guī)劃的預(yù)處理速度以及預(yù)處理之后的求解速度變得更快。由此可見，線性規(guī)劃問題約束矩陣A的稀疏程度越高越有利于問題的求解。因此，在本文以稀疏存儲為背景的前提下，處理比例行時的第二個原則就是盡可能的減少非零元素的個數(shù)。綜上，本文對比例行的處理基于的兩個基本原則是：

(1)盡可能的增加單獨列的數(shù)目；

(2)盡可能的減少非零元素的個數(shù)。

5.2對兩個約束行構(gòu)成比例關(guān)系的處理

如圖2所示，第i行與第k行構(gòu)成比例關(guān)系，即除了各自所含有的單獨列元素之外，兩行的其他對應(yīng)元素之間僅差一個常數(shù)因子。為此，本文首先把第i行和第k行所含有的非零元素分為四個部分，即第i行所含的單獨列元素部分(圖中的Mi模塊)、第k行所含的單獨列元素部分(圖中的Mk模塊)、i行與k行所含的二元列元素部分(圖中的N1模塊)和第i行與k行所含的多元列(大于2)元素部分(圖中的N2模塊)。Mi、Mk、N1、N2均為相應(yīng)的列標(biāo)號的集合，分別用|Mi|、|Mk|、|N1|、|N2|表示這四個集合所含的約束矩陣列的個數(shù)。

圖2 兩行成比例時非零元素的分布

構(gòu)成比例關(guān)系的第i行和第k行如下所示：

假設(shè)以i行為基準(zhǔn)行，從k行中消除與i行構(gòu)成比例的部分。把i行的-v倍加到第k行，得到:

從上式可以看出，把第i行的-v倍加到第k行之后，第k行中的屬于N1和N2的部分全部消掉，第i行與第k行構(gòu)成的二元列變成單獨列，而第i行中原來屬于單獨列的部分變成二元列。因而，本次消除操作增加的單獨列的個數(shù)為|N1|，減少的單獨列的個數(shù)為|Mi|；增加的非零元素的個數(shù)為|Mi|，減少的非零元素的個數(shù)為|N1|+|N2|。根據(jù)原則(1)與原則(2)的要求，若該操作被執(zhí)行，以下條件需要滿足：

(α)與(β)不能同時取等號，否則消除操作沒有意義。顯然，若(α)不取等號，原則(1)滿足，原則(2)必然滿足；若(α)取等號，只要N2不是空集，則原則(1)與原則(2)都滿足。若條件(*)不滿足，則說明以i行作為基準(zhǔn)行，對k行采取消除操作的處理方法不可行。因而只能嘗試采取以k行為基準(zhǔn)行，推導(dǎo)過程與以上類似。如果k行也不滿足消除條件(*)，則不進(jìn)行消除操作。如果i行和k行都滿足條件(*)，則選擇含有單獨列較少者作為基準(zhǔn)行。如果兩行都不含有單獨列，則選取任意一行作為基準(zhǔn)行。

在線性規(guī)劃預(yù)處理中，比例行的檢測和處理往往要進(jìn)行多次，對于構(gòu)成比例關(guān)系的兩個約束行，在對它們已經(jīng)進(jìn)行了比例行消除操作之后，在下一次的比例行檢測和處理中，如果N2是空集它們依然構(gòu)成比例關(guān)系，那么之前的消除操作是否會被還原？下面的定理將告訴我們，在下一次比例行檢測和處理的過程中不會出現(xiàn)對之前比例消除操作的還原。繼續(xù)以上文中構(gòu)成比例關(guān)系的i行與k行為例，假設(shè)以i行為基準(zhǔn)行，在k行中實施了比例消除操作。

定理：若第i行與第k行在下一次比例行預(yù)處理中仍然被檢測出存在比例關(guān)系(即|N2|=0)，若繼續(xù)使用原則1和原則2作為是否進(jìn)行消除操作的依據(jù)，則不會出現(xiàn)對上一次比例消除操作的還原。

證明：由于在第一次執(zhí)行消除操作時原則(1)與原則(2)已經(jīng)被滿足，且又一次檢測出存在比例關(guān)系，因而顯然有|N2|=0且|N1|>|Mi|。在第二次檢測中，二元列的數(shù)目是|Mi|，多元列的數(shù)目是0，第i行含有的單獨列的數(shù)目是|N1|，第k行含有的單獨列的數(shù)目是|M2|，應(yīng)用原則1與原則2我們可以得：如果消除操作能被執(zhí)行的話，條件(*)需要滿足，即|Mi|>|N1|需要滿足，而這是不可能的。因此，應(yīng)用原則(1)和原則(2)，即使第二次被檢測到存在比例關(guān)系，也不會出現(xiàn)對先前比例消除操作的還原。

5.3對多個約束行(≥3)構(gòu)成比例關(guān)系的處理

本文以3個約束行構(gòu)成比例關(guān)系為例，來說明對多個約束行構(gòu)成比例關(guān)系的處理。對于n(n>3)個約束行構(gòu)成比例關(guān)系的消除處理，與對3個約束行構(gòu)成比例關(guān)系的處理類似。

如圖3所示，i行、k行和h行三行存在比例關(guān)系，構(gòu)成比例行。根據(jù)比例行的定義，與對兩行構(gòu)成比例關(guān)系的處理類似，本文首先把i、k、h三行所含有的所有非零元素分為五個部分，即第i行含有的單獨列部分(圖中的Mi模塊)、第k行含有的單獨列部分(圖中的Mk模塊)、第h行含有的單獨列部分(圖中的Mh模塊)、第i、k、h行所含有的三元列部分(圖中的N1模塊)和第i、k、h行所含有的多元列(大于3)部分(圖中的N2模塊)。Mi、Mk、Mh、N1、N2均為相應(yīng)的列標(biāo)號的集合，分別用|Mi|、|Mk|、|Mh|、|N1|、|N2|表示這五個集合所含的約束矩陣列的個數(shù)。

圖3 三行成比例時非零元素的分布

在處理兩個約束行構(gòu)成的比例關(guān)系時，由于構(gòu)成比例關(guān)系的約束行只有兩行，因而只需要執(zhí)行一次消除操作。具體選擇哪一行作為基準(zhǔn)行，只需根據(jù)消除原則(1)和原則(2)選擇即可。而在處理多個約束行構(gòu)成的比例關(guān)系時，由于需要執(zhí)行多次消除操作(至少兩次)，因而需要考慮所有的消除操作是選用相同的基準(zhǔn)行，還是不同的消除操作選用不同的基準(zhǔn)行。因此，本文下面將從多次消除操作固定基本行和變基本行兩個方面，來分析在處理多個約束行構(gòu)成的比例關(guān)系時，基本行的選取以及消除操作如何執(zhí)行的問題。

5.3.1 固定基準(zhǔn)行消除操作

假設(shè)第i行被選為執(zhí)行消除操作的基準(zhǔn)行。則第i行將保持不變，第h行和第k行中與i行成比例的部分將被消除。第i行中所含有的單獨列變成三元列，由i、k、h三行所構(gòu)成的三元列變成了單獨列。因此，增加的非零元素個數(shù)為2|Mi|，減少的非零元素個數(shù)為2(|N1|+|N2|)，增加的單獨列的個數(shù)為|N1|，減少的單獨列的個數(shù)為|Mi|。應(yīng)用消除原則1和原則2，如果假設(shè)成立，消除操作能被執(zhí)行，則需要滿足下列條件：

(*)

(α)與(β)不能同時取等號。觀察上式(α)(β)可得，不等式的左邊與基準(zhǔn)行沒有關(guān)系，只有不等式的右邊才由基準(zhǔn)行所決定，因而不難得出：如果在構(gòu)成比例關(guān)系的行簇中，只有某一行作為基準(zhǔn)時，消除操作的原則(1)(2)才能被滿足，則選擇該行作為基準(zhǔn)行。

如果有多個(至少兩個)約束行都能滿足消除操作的原則(1)和原則(2)((*))，究竟應(yīng)該選擇哪個行作為消除操作的基準(zhǔn)行，下面將開始分析。

令集合R為構(gòu)成比例關(guān)系的一簇行的行標(biāo)的集合，集合J為R中滿足消除原則的行標(biāo)的集合(J?G)，則選取集合J中的任一行j作為基準(zhǔn)行，增加的單獨列和非零元素分別為|N1|-|Mj|和2(|N1|+|N2|-|Mj|)(j∈J)，根據(jù)消除原則，應(yīng)該選擇使得單獨列增加最多，且非零元素減少最多的行作為基準(zhǔn)行。

如果j滿足j=argmaxl∈J{|N1|-|Ml|},并且j=argmaxl∈J{2(|N1|+|N2|-|Ml|),即如果j滿足j=argminl∈J{|Ml|},則選擇第j行作為基準(zhǔn)行。若J為空集，則不進(jìn)行消除操作。

因此，在固定基本行消除操作中，選擇滿足條件(*)且含有單獨列數(shù)目最少的行作為基準(zhǔn)行，可以產(chǎn)生更多的單獨列，減少更多的非零元素。

5.3.2 變基準(zhǔn)行消除操作

以三個約束行構(gòu)成比例行為例，若消除原則全部滿足，則需要進(jìn)行兩次消除操作，假設(shè)第一次消除操作以第i行為基本行，保持第i行不變，在第k行中按照比例關(guān)系實施消除操作。第二次消除操作以第h行為基本行，保持第h行不變，在i行中按照比例關(guān)系實施消除操作。

第一次消除操作減少的非零元素的個數(shù)是|N1|+|N2|-|Mi|，單獨列數(shù)目非但沒有增加，反而減少了|Mi|個單獨列。第二次消除操作減少的非零元素的個數(shù)是|N1|+|N2|-|Mh|，與第一次消除操作類似，減少了|Mh|個單獨列。兩次消除操作共減少的非零元素的個數(shù)是2(|N1|+|N2|)-|Mi|-|Mh|，增加的單獨列的個數(shù)是|N1|-(|Mi|+|Mh|)。

由5.3.1的分析可知，若采用固定基準(zhǔn)行處理三約束行構(gòu)成的比例關(guān)系，減少的非零元素的個數(shù)是maxl∈J{|N1|-|Ml|},增加的單獨列的個數(shù)是maxl∈J{2(|N1|+|N2|-|Ml|)。

比較固定基準(zhǔn)行與變基準(zhǔn)行消除操作的處理結(jié)果如下:

不難看出對于任意的i和h，上式均成立。

因此，通過以上分析可知，在處理多個約束行構(gòu)成的比例關(guān)系時，采用固定基準(zhǔn)行進(jìn)行消除操作優(yōu)于采用變基準(zhǔn)行進(jìn)行消除操作。所以本文在處理多約束行構(gòu)成的比例關(guān)系時，采用固定基準(zhǔn)行進(jìn)行消除操作。

6 數(shù)值試驗及結(jié)果分析

為了進(jìn)一步驗證基于十字鏈表的稀疏存儲，以及在此基礎(chǔ)上的比例行檢測和處理方法，本文首先通過一個微型算例對比例行檢測和處理的具體過程進(jìn)行了演示和分析，然后通過Netlib數(shù)據(jù)庫中的6個實際線性規(guī)劃問題，對比例行檢測和處理方法真正作用于超大規(guī)模線性規(guī)劃問題時的效果進(jìn)行了驗證。

6.1比例行檢測和處理過程的演示和分析

假設(shè)約束矩陣采用本文所提出的基于十字鏈表的稀疏存儲?？紤]如下的約束矩陣A和資源約束向量b。

Ax=b

(1)

比例行檢測過程見表2。

表2 約束矩陣A的比例行檢測過程

從i=0到i=4的檢測過程中，所有行的CA值和SA值的變化過程如上表所示。由于約束矩陣A的后6列全是單獨列，故在進(jìn)行比例行檢測時，從第4列起只需檢查十字鏈表的列表頭節(jié)點，不再檢測非零元素節(jié)點，因而從i=4到i=9的檢測過程中，所有行的CA值和SA值保持不變。隱去部分的CA值和SA值與i=4時的值完全相同。并且，在檢測過程中只需要檢測前3列的11個非零元素，這使得檢測效率大大提高。

從以上最后的檢測結(jié)果可以看出，約束矩陣A存在兩個成比例的行簇，第一個由第1、2行構(gòu)成，第二個由第3、4、5行構(gòu)成，而第6行不與任何行構(gòu)成比例關(guān)系。

應(yīng)用比例行處理方法對檢測出的兩個比例行簇進(jìn)行處理，處理過程及結(jié)果如下。

處理第1行和第2行：|N1|=1, |N2|=1, |M1|=1, |M2|=2,由于|N1|=|M1|且|N1|+|N2|>|M1|,因而選取第1行作為基準(zhǔn)行，第1行保持不變，在第2行中減去2倍的第1行。

處理第3、4、5行：|N1|=1, |N2|=1, |M3|=2, |M4|=1, |M5|=0，盡管第4行和第5行同時滿足判定條件(*)，但是由于|M5|<|M4|, 因而選第5行作為基準(zhǔn)行保持不變，從第3行、第4行中分別減去第5行的1/3倍和2/3倍。對兩個比例行簇處理之后的結(jié)果如下：

A′x=b′

(2)

對比(1)(2)不難發(fā)現(xiàn)，經(jīng)過處理，約束矩陣的非零元素從17個下降到12個，單獨列的個數(shù)從6個增加到7個。

6.2作用于超大規(guī)模線性規(guī)劃問題時的效果

如表3所示，本文從Netlib數(shù)據(jù)庫中選取了6個規(guī)模由小變大的實際線性規(guī)劃問題，對比例行檢測和處理方法的實際應(yīng)用效果進(jìn)行了驗證。從結(jié)果可以看出，本文提出的比例行檢測和處理方法能夠有效的檢測約束矩陣中存在的比例行，能夠?qū)Ρ壤羞M(jìn)行有效的處理，從而使得約束矩陣的非零元素增加、單獨列不減。

表3 比例行檢測和處理方法的實際應(yīng)用效果

綜上，本文提出的基于十字鏈表的稀疏存儲，以及在此基礎(chǔ)上的比例行檢測和處理方法的可行性和有效性得到了驗證。

7 結(jié)語

隨著大數(shù)據(jù)時代的到來，線性規(guī)劃問題的規(guī)模越來越大是一種必然。盡管近年來硬件的發(fā)展使得計算機(jī)的存儲能力有了突飛猛進(jìn)的增長，但是，如何節(jié)省存儲空間、提高計算效率依然是非常值得研究的問題，尤其是當(dāng)面對超大規(guī)模線性規(guī)劃問題時。

本文所提出的基于對傳統(tǒng)做了改進(jìn)的十字鏈表的稀疏存儲方式，不僅節(jié)省了存儲空間，而且極大的方便了線性規(guī)劃的數(shù)據(jù)查詢、修改和增刪等操作。并且，在此存儲結(jié)構(gòu)的基礎(chǔ)上，本文提出的比例行檢測方法和處理方法，不僅方法本身簡單易操作，而且在消除比例冗余的同時，一方面減少了非零元素的個數(shù)，一方面增加了單獨列的個數(shù)。非零元素個數(shù)的減少使得約束矩陣的稀疏程度增加，從而節(jié)省了存儲空間；單獨列數(shù)目的增加，將有利于部分決策變量的可行域被縮小或者直接求出結(jié)果，從而使得超大規(guī)模線性規(guī)劃問題的規(guī)模被縮小。

在針對比例關(guān)系稀少的小規(guī)模線性規(guī)劃問題時，本文提出的存儲結(jié)構(gòu)和比例行處理方法或許優(yōu)勢不明顯，甚至可能沒有應(yīng)用的必要，但是在面對比例關(guān)系稠密的超大規(guī)模線性規(guī)劃問題時，規(guī)模越大、比例關(guān)系越稠密，它們的作用就越明顯。

[1] 藍(lán)伯雄，王童姝.大規(guī)?？瓦\專線網(wǎng)絡(luò)運營化模型與求解算法[J].中國管理科學(xué)，2016,24(6):159-170.

[2] 許啟發(fā), 蔡超, 蔣翠俠. 指令不均衡與股票收益關(guān)系研究—基于大規(guī)模數(shù)據(jù)分位數(shù)回歸的實證[J].中國管理科學(xué),2016,24(12):20-29.

[3] 李暉, 黃南京, 葉一軍, 基于時空約束的大規(guī)模農(nóng)產(chǎn)品時間柔性生產(chǎn)計劃網(wǎng)絡(luò)優(yōu)化研究[J].中國管理科學(xué), 2015,23 (4): 157-166.

[4] 阮俊虎, 王旭坪, 楊挺, 大規(guī)模災(zāi)害中基于聚類的醫(yī)療物資聯(lián)合運送優(yōu)化[J].中國管理科學(xué) 2014,22 (10): 80-89.

[5] 陳驥, 蘇為華, 張崇輝.基于屬性分布信息的大規(guī)模群體評價方法及應(yīng)用[J].中國管理科學(xué) 2013,21 (3): 146-152.

[6] 孫貴吉, 曹曉威.大規(guī)模線性優(yōu)化系統(tǒng)的設(shè)計與實現(xiàn)[J].吉林大學(xué)學(xué)報, 2004,22(3): 258-259.

[7] 成孟金, 趙飛.線性規(guī)劃模型預(yù)處理的研究與實現(xiàn)[J].甘肅科技,2008,24(23):87-89.

[8] Gondzio J, Terlaky T. A computational view of interior-point methods for linear programming[J]. Advanced in Linear and Integer Programming,1995, 36(3): 103-144.

[9] Andersen E D, Andersen K D. Presolving in linear programming [J]. Math Programming, 1995,71(2): 221-245.

[10] Gondzio J.Presolve analysis of linear programs prior to applying an interior point method[R].Technical Report,Department of Management Studies,University of Geneva, Switzerland,1994.

[11] 胡艷杰，黃思明，Adrien N,et al.對偶性在線性規(guī)劃預(yù)處理中的應(yīng)用分析[J].中國管理科學(xué)，2016,24(12):117-126.

[12] 肖宏啟.數(shù)據(jù)結(jié)構(gòu)[M].清華:清華大學(xué)出版社，2016.

[13] Adler I, Karmarkar N, Resende M G C, Veiga G. Data structures and programming techniques for the implementation of karmarkar's algorithm[J] ORSA: Journal on Computing, 1989:1(2):84-106.

[14] Tomlin L A, Welch J S. Finding duplicate rows in a linear programming model[J]. Operations Research Letters, 1986,5(1):7-1.

SparseStorageforSuper-large-scaleLinearProgrammingandMethodsforIdentifyingandDisposingofDuplicateRowsinitsPresolving

WUYu1,2,HUANGSi-ming1

(1.Institutes of Science and Development, Chinese Academy of Sciences, Beijing 100190, China;2.University of Chinese Academy of Sciences, Beijing 100049, China)

With the arrival of the big data era, it is certain and inevitable that the size of linear programming problem is becoming bigger and bigger. In response to super-large-scale linear programming problems, in order to save the storage space,avoid waste of resources, and make the data’s inspecting, modifying and striking out more convenient, how to store data is an urgent and important problem. In this paper, a data structure for data’s sparse storage is proposed, which is based on improved Orthogonal List. The performance of this method on saving storage space is verified by some super-large-scale linear programming cases from the Netlib database. Furthermore, due to the existing of much redundant data, a presolving process is often required before algorithm is used to solve the linear programming problem. Identifying and disposing of duplicate rows is one of the key steps. In this paper, the methods for identifying and disposing the duplicate rows are proposed. Firstly, the definition of duplicate rows and other related concepts are given. Duplicate rows’ definition is different from common sense, in which columns with only one non-zero element have not been take into account. Secondly, combined with the proposed data storage structure, a simple method for identifying duplicate rows is proposed, which is based on classification thought and is very easy to operate.It only needs to inspect one time from the first column to the last column. Thirdly, by summarizing the existing related literature, two basic principles for eliminating redundant rows are obtained. The first step is to increase the number of one-element columns as much as possible, and the second is to reduce the number of the non-zero elements as much as possible. Then, based on these two principles, the nonzero elements of duplicate rows are classified into different sets and further the number of nonzero elements within each set is theoretically analyzed. A method for disposing of duplicate row is obtained, which not only guarantee the data’s sparse degree, but also increase the number of one-element column. In the last part, firstly, through applying the proposed methods on a mini linear programming example, the concrete process of Identifying and Disposing of Duplicate Rows is exemplified. Secondly, by applying the proposed methods on some concrete linear programming cases which are selected from the Netlib database, the effectiveness of the methods is verified. From the result, it can be seen that when the proposed data structure and the methods are applied on small-scale linear programming problems or linear programming problem with little duplicate rows, their advantage may be negligible or not obvious. However, when in response to large-scale linear programming problems with dense duplicate rows, the larger the scale or the denser the duplicate rows, the more obvious the effectiveness is.

1003-207(2017)10-0100-09

10.16381/j.cnki.issn1003-207x.2017.10.011

O221.1

A

2016-06-30；

2017-02-14

武昱(1986-)，男(漢族)，甘肅人，中國科學(xué)院博士研究生，研究方向：大規(guī)模線性規(guī)劃及在線算法，E-mail:wuyu14@mails.ucas.edu.cn.

Keywords： linear programming; presolving; orthogonal List; sparse storage; duplicate rows