主管:中国科学院
主办:中国优选法统筹法与经济数学研究会
   中国科学院科技战略咨询研究院
Articles

Sparse Storage for Super-large-scale Linear Programming and Methods for Identifying and Disposing of Duplicate Rows in its Presolving

Expand
  • 1. Institutes of Science and Development, Chinese Academy of Sciences, Beijing 100190, China;
    2. University of Chinese Academy of Sciences, Beijing 100049, China

Received date: 2016-06-30

  Revised date: 2017-02-14

  Online published: 2017-12-15

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.

Cite this article

WU Yu, HUANG Si-ming . Sparse Storage for Super-large-scale Linear Programming and Methods for Identifying and Disposing of Duplicate Rows in its Presolving[J]. Chinese Journal of Management Science, 2017 , 25(10) : 100 -108 . DOI: 10.16381/j.cnki.issn1003-207x.2017.10.011

References

[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.
Outlines

/