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

武 昱，黃思明

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

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

武 昱1,2，黃思明1

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

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

線性規劃；預處理；十字鏈表；稀疏存儲；比例行

1 引言

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

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

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

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

2 基本模型及相關概念的定義

通常的線性規劃模型如下：

用矩陣形式表示如下：

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

在以上的線性規劃模型中，矩陣A被稱為約束矩陣，行向量c被稱為價值系數向量，列向量b被稱為資源約束向量。基于這些基本概念，下面給出本文所討論的比例行及其他相關概念的定義。

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

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

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

消除操作：若兩約束行構成比例行，依據比例關系，從其中一個約束行的兩邊等價地消去與另一行構成比例的部分，這一操作稱為消除操作。

3 超大規模線性規劃問題數據的存儲

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

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

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

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

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

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

4 比例行的檢測

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

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

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

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

比例行檢測方法如下：

步驟1：設置i=0,c=1；

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

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

①如果等于1，重復執行步驟2；

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

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

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

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

5 比例行的處理

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

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

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

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

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

5.1比例行處理的基本原則

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

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

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

5.2對兩個約束行構成比例關系的處理

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

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

構成比例關系的第i行和第k行如下所示：

假設以i行為基準行，從k行中消除與i行構成比例的部分。把i行的-v倍加到第k行，得到:

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

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

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

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

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

5.3對多個約束行(≥3)構成比例關系的處理

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

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

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

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

5.3.1 固定基準行消除操作

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

(*)

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

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

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

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

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

5.3.2 變基準行消除操作

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

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

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

比較固定基準行與變基準行消除操作的處理結果如下:

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

因此，通過以上分析可知，在處理多個約束行構成的比例關系時，采用固定基準行進行消除操作優于采用變基準行進行消除操作。所以本文在處理多約束行構成的比例關系時，采用固定基準行進行消除操作。

6 數值試驗及結果分析

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

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

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

Ax=b

(1)

比例行檢測過程見表2。

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

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

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

應用比例行處理方法對檢測出的兩個比例行簇進行處理，處理過程及結果如下。

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

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

A′x=b′

(2)

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

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

如表3所示，本文從Netlib數據庫中選取了6個規模由小變大的實際線性規劃問題，對比例行檢測和處理方法的實際應用效果進行了驗證。從結果可以看出，本文提出的比例行檢測和處理方法能夠有效的檢測約束矩陣中存在的比例行，能夠對比例行進行有效的處理，從而使得約束矩陣的非零元素增加、單獨列不減。

表3 比例行檢測和處理方法的實際應用效果

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

7 結語

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

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

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

[1] 藍伯雄，王童姝.大規模客運專線網絡運營化模型與求解算法[J].中國管理科學，2016,24(6):159-170.

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

[3] 李暉, 黃南京, 葉一軍, 基于時空約束的大規模農產品時間柔性生產計劃網絡優化研究[J].中國管理科學, 2015,23 (4): 157-166.

[4] 阮俊虎, 王旭坪, 楊挺, 大規模災害中基于聚類的醫療物資聯合運送優化[J].中國管理科學 2014,22 (10): 80-89.

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

[6] 孫貴吉, 曹曉威.大規模線性優化系統的設計與實現[J].吉林大學學報, 2004,22(3): 258-259.

[7] 成孟金, 趙飛.線性規劃模型預處理的研究與實現[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.對偶性在線性規劃預處理中的應用分析[J].中國管理科學，2016,24(12):117-126.

[12] 肖宏啟.數據結構[M].清華:清華大學出版社，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-)，男(漢族)，甘肅人，中國科學院博士研究生，研究方向：大規模線性規劃及在線算法，E-mail:wuyu14@mails.ucas.edu.cn.

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