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 条
  • [1] Branch-and-bound algorithm for the maximum triangle packing problem
    Abdelsadek, Youcef
    Herrmann, Francine
    Kacem, Imed
    Otjacques, Benoit
    [J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 81 : 147 - 157
  • [2] [Anonymous], 2012, International Review of Pure and Applied Mathematics
  • [3] Bazaraa M. S., 2009, LINEAR PROGRAMMING N, P1
  • [4] Beale E.M.L., 1955, NAVAL RES LOGISTICS, V2, P269, DOI [DOI 10.1002/NAV.3800020406, 10.1002/nav.3800020406]
  • [5] Bland R. G., 1977, Mathematics of Operations Research, V2, P103, DOI 10.1287/moor.2.2.103
  • [6] Dantzig G. B., 1955, Pacific Journal of Mathematics, V5, P183
  • [7] Dantzig GB., 1951, Activity analysis of production and allocation, P339
  • [8] Diaz J. C. Z., 2010, Advances in Information Sciences and Service Sciences, V2, P67
  • [9] Kachiyan L. G., 1979, SOV MATH DOKL, V4, P373
  • [10] A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING
    KARMARKAR, N
    [J]. COMBINATORICA, 1984, 4 (04) : 373 - 395
123