Sparsity Prevention Pivoting Method for Linear Programming

被引：0
作者：
Li, Peiqiang [1 ]
Li, Qiyuan [1 ,2 ]
Li, Canbing [1 ,2 ]
Zhou, Bin [1 ,2 ]
Cao, Yijia [1 ,2 ]
Wu, Qiuwei [3 ]
Fang, Baling [2 ,4 ]
机构：
[1] Hunan Univ, Coll Elect & Informat Engn, Changsha 410082, Hunan, Peoples R China
[2] Hunan Univ, Hunan Key Lab Intelligent Informat Anal & Integra, Changsha 410082, Hunan, Peoples R China
[3] Tech Univ Denmark, Ctr Elect Power & Energy, Dept Elect Engn, DK-2800 Lyngby, Denmark
[4] Hunan Univ Technol, Coll Elect & Informat Engn, Zhuzhou 412007, Peoples R China
来源：
IEEE ACCESS | 2018年 / 6卷
基金：
中国国家自然科学基金;
关键词：
Linear programming; pivoting rules; simplex algorithm; sparse matrix; SIMPLEX ALGORITHM; DEFICIENT-BASIS; MODELS;
D O I：
10.1109/ACCESS.2018.2817571
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
When the simplex algorithm is used to calculate a linear programming (LP) problem, if the matrix is a sparse matrix, it will be possible to lead to many zero-length calculation steps, and even iterative cycle will appear. To deal with the problem, a new pivoting method is proposed in this paper. The principle of this method is to avoid choosing the row which the value of the element in the right side of constraint expression for LP in this row is zero as the row of the pivot element to make the matrix in LP density and ensure that most subsequent steps will improve the value of the objective function. One step following this principle is inserted in the existing LP algorithm to reselect the pivot element. Both the conditions for inserting this step and the maximum number of allowed insertion steps are determined. In the case study, taking several numbers of LP problems as examples, the results indicate that this method can effectively improve the efficiency of LP for the sparse matrix.
引用
收藏
页码：19560 / 19567
页数：8
相关论文
共 24 条
123