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

武 昱，黃思明

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

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

武 昱1,2，黃思明1

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

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

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

1 引言

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

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

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

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

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被稱為價(jià)值系數(shù)向量，列向量b被稱為資源約束向量?；谶@些基本概念，下面給出本文所討論的比例行及其他相關(guān)概念的定義。

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

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

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

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

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

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

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

圖1 基于十字鏈表稀疏存儲(chǔ)的示意圖

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

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

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

4 比例行的檢測(cè)

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

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

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

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

比例行檢測(cè)方法如下：

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

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

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

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

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

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

步驟3：按照十字鏈表的列指針，依次掃描第i列的ci個(gè)非零元素：設(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, 檢測(cè)CA的值， CA值為-INF的行不與其他任何行構(gòu)成比例行，具有相同CA(不等于-INF)值的行相互之間構(gòu)成比例關(guān)系。比例行檢測(cè)結(jié)束。

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

5 比例行的處理

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

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

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

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

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

5.1比例行處理的基本原則

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

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

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

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

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

圖2 兩行成比例時(shí)非零元素的分布

構(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)成的二元列變成單獨(dú)列，而第i行中原來(lái)屬于單獨(dú)列的部分變成二元列。因而，本次消除操作增加的單獨(dú)列的個(gè)數(shù)為|N1|，減少的單獨(dú)列的個(gè)數(shù)為|Mi|；增加的非零元素的個(gè)數(shù)為|Mi|，減少的非零元素的個(gè)數(shù)為|N1|+|N2|。根據(jù)原則(1)與原則(2)的要求，若該操作被執(zhí)行，以下條件需要滿足：

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

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

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

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

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

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

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

圖3 三行成比例時(shí)非零元素的分布

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

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

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

(*)

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

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

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

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

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

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

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

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

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

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

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

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

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

6.1比例行檢測(cè)和處理過(guò)程的演示和分析

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

Ax=b

(1)

比例行檢測(cè)過(guò)程見表2。

表2 約束矩陣A的比例行檢測(cè)過(guò)程

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

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

應(yīng)用比例行處理方法對(duì)檢測(cè)出的兩個(gè)比例行簇進(jìn)行處理，處理過(guò)程及結(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行同時(shí)滿足判定條件(*)，但是由于|M5|<|M4|, 因而選第5行作為基準(zhǔn)行保持不變，從第3行、第4行中分別減去第5行的1/3倍和2/3倍。對(duì)兩個(gè)比例行簇處理之后的結(jié)果如下：

A′x=b′

(2)

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

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

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

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

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

7 結(jié)語(yǔ)

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

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

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

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

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

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

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

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

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

[7] 成孟金, 趙飛.線性規(guī)劃模型預(yù)處理的研究與實(shí)現(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.對(duì)偶性在線性規(guī)劃預(yù)處理中的應(yīng)用分析[J].中國(guó)管理科學(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-)，男(漢族)，甘肅人，中國(guó)科學(xué)院博士研究生，研究方向：大規(guī)模線性規(guī)劃及在線算法，E-mail:wuyu14@mails.ucas.edu.cn.

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