关键词: 线性规划, 预处理, 十字链表, 稀疏存储, 比例行

Abstract: 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.

Key words: linear programming, presolving, orthogonal List, sparse storage, duplicate rows