Sparsity Prevention Pivoting Method for Linear Programming

CCMA PDEs and Numerical Methods Seminar Series

Meeting Details

You must log in to see who to contact about this meeting.

Speaker: Canbing Li,

Abstract: LP is a basic problem in optimization. Most of practical problems need to call LP in their iterations. Therefore, the improvement of LP solutions can contribute to almost all of optimization solutions. Simplex algorithm is a basic and effective solution for LP problems. When the matrix is a sparse matrix, it will be possible to lead to many zero-length calculation steps. There is also an example with endless loops. To deal with the problem, a new pivoting method is proposed. 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 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. 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 proposed method is simple and effective.


Room Reservation Information

Room Number: 315 McAllister

Date: 11/16/2018

Time: 2:00pm - 3:00pm