武 昱，黄思明

(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