Sparsity Prevention Pivoting Method for Linear Programming | Zendy

Peiqiang Li | Zendy; Qiyuan Li | Zendy; Canbing Li | Zendy; Bin Zhou | Zendy; Yijia Cao | Zendy; Qiuwei Wu | Zendy; Baling Fang | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Sparsity Prevention Pivoting Method for Linear Programming

Author(s) -

Peiqiang Li,

Qiyuan Li,

Canbing Li,

Bin Zhou,

Yijia Cao,

Qiuwei Wu,

Baling Fang

Publication year - 2018

Publication title -

ieee access

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.587

H-Index - 127

ISSN - 2169-3536

DOI - 10.1109/access.2018.2817571

Subject(s) - aerospace , bioengineering , communication, networking and broadcast technologies , components, circuits, devices and systems , computing and processing , engineered materials, dielectrics and plasmas , engineering profession , fields, waves and electromagnetics , general topics for engineers , geoscience , nuclear engineering , photonics and electrooptics , power, energy and industry applications , robotics and control systems , signal processing and analysis , transportation

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research