【摘要】：隨著大數(shù)據(jù)時代的到來,線性規(guī)劃問題的規(guī)模越來越大是一種必然。面對超大規(guī)模線性規(guī)劃問題,如何存儲數(shù)據(jù),使得存儲空間節(jié)省以避免資源的浪費,并且使得數(shù)據(jù)的查詢、修改和增刪方便快捷,是一個急需解決的問題。本文提出了基于十字鏈表的數(shù)據(jù)稀疏存儲方式。并且,通過對Netlib數(shù)據(jù)庫中的超大規(guī)模線性規(guī)劃問題進行存儲分析,對此種存儲方式的優(yōu)越性進行了驗證。此外,由于大量冗余數(shù)據(jù)的存在,在應(yīng)用算法求解超大規(guī)模線性規(guī)劃問題之前,往往需要進行預(yù)處理,而比例行的檢測和處理是預(yù)處理中必要的關(guān)鍵一步,因此本文提出了比例行的檢測和處理方法。首先給出了不同于常理的比例行及其他相關(guān)概念的定義;然后結(jié)合本文提出的數(shù)據(jù)存儲方式,提出了簡單易操作的比例行檢測方法;接著總結(jié)已有文獻得出了比例行消除操作的兩個基本原則,并在此基礎(chǔ)上通過對比例行所含有的非零元素進行分類,通過理論分析推導(dǎo)出了保證約束矩陣稀疏度不降且單獨列增加的比例行處理方法。最后,首先通過一個微型算例對比例行檢測和處理的具體過程進行了演示和分析,然后通過Netlib數(shù)據(jù)庫中的6個實際線性規(guī)劃問題,對比例行檢測和處理方法真正作用于超大規(guī)模線性規(guī)劃問題時的效果進行了驗證。
[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.
【作者單位】： 中國科學(xué)院科技戰(zhàn)略咨詢研究院;中國科學(xué)院大學(xué);
【分類號】：O221.1

【相似文獻】

相關(guān)期刊論文 前6條

1 尚毅;于忠卓;邵和平;;一種新的大規(guī)模線性規(guī)劃及線性方程組的迭代算法[J];遼寧大學(xué)學(xué)報(自然科學(xué)版);1986年04期

2 敖文仲 ,李漢鈴 ,王國慶;在微機上用分塊法求解大規(guī)模線性規(guī)劃問題的改進[J];管理現(xiàn)代化;1987年01期

3 趙鳳治;解大規(guī)模線性規(guī)劃問題的某些技巧[J];數(shù)值計算與計算機應(yīng)用;1992年01期

4 吳健中;賀立群;;一類大規(guī)模線性規(guī)劃問題的分解協(xié)調(diào)算法[J];系統(tǒng)工程學(xué)報;1987年01期

5 王武義,萬百五,曾建潮;大規(guī)模線性規(guī)劃的OPBM遞階解法[J];系統(tǒng)工程;1987年02期

6 曾建潮;萬百五;;大規(guī)模線性規(guī)劃問題的分解—協(xié)調(diào)算法[J];系統(tǒng)工程學(xué)報;1986年01期

，

本文編號：2384556