超大规模线性规划的稀疏存储和预处理中比例行的检测和处理方法

发布时间：2018-12-17 17:26

【摘要】：随着大数据时代的到来,线性规划问题的规模越来越大是一种必然。面对超大规模线性规划问题,如何存储数据,使得存储空间节省以避免资源的浪费,并且使得数据的查询、修改和增删方便快捷,是一个急需解决的问题。本文提出了基于十字链表的数据稀疏存储方式。并且,通过对Netlib数据库中的超大规模线性规划问题进行存储分析,对此种存储方式的优越性进行了验证。此外,由于大量冗余数据的存在,在应用算法求解超大规模线性规划问题之前,往往需要进行预处理,而比例行的检测和处理是预处理中必要的关键一步,因此本文提出了比例行的检测和处理方法。首先给出了不同于常理的比例行及其他相关概念的定义;然后结合本文提出的数据存储方式,提出了简单易操作的比例行检测方法;接着总结已有文献得出了比例行消除操作的两个基本原则,并在此基础上通过对比例行所含有的非零元素进行分类,通过理论分析推导出了保证约束矩阵稀疏度不降且单独列增加的比例行处理方法。最后,首先通过一个微型算例对比例行检测和处理的具体过程进行了演示和分析,然后通过Netlib数据库中的6个实际线性规划问题,对比例行检测和处理方法真正作用于超大规模线性规划问题时的效果进行了验证。
[Abstract]:With the arrival of big data era, the scale of linear programming is becoming larger and larger. Facing the problem of super large scale linear programming, how to store data, save storage space to avoid the waste of resources, and make the query, modification, addition and deletion of data convenient and fast, is an urgent problem to be solved. In this paper, a data sparse storage method based on cross-linked list is proposed. Furthermore, the superiority of this storage method is verified by analyzing the large scale linear programming problem in Netlib database. In addition, due to the existence of a large amount of redundant data, it is often necessary to preprocess the algorithm before solving the problem of super-large scale linear programming, and the detection and processing of proportional rows is a necessary and crucial step in the preprocessing. Therefore, this paper puts forward the detection and processing method of proportional line. The definition of scale line and other related concepts, which is different from common sense, is first given, and then a simple and easy to operate proportional line detection method is proposed, which is based on the data storage method proposed in this paper. Then, two basic principles of proportional row elimination operation are obtained by summarizing the existing literature, and on this basis, the non-zero elements contained in the routine are compared and classified. Based on the theoretical analysis, the proportional row processing method is derived to ensure that the sparse degree of constraint matrix is not reduced and the columns are increased separately. At last, the detailed process of routine detection and processing is compared and analyzed by a micro-example, and then the six practical linear programming problems in Netlib database are presented and analyzed. The effectiveness of routine detection and processing methods for large scale linear programming problems is verified.
【作者单位】：中国科学院科技战略咨询研究院;中国科学院大学;
【分类号】：O221.1

【相似文献】