An efficient simplex type algorithm for sparse and dense linear programs

An efficient simplex type algorithm for sparse and dense linear programs

0.00 Avg rating0 Votes
Article ID: iaor20042841
Country: Netherlands
Volume: 148
Issue: 2
Start Page Number: 323
End Page Number: 334
Publication Date: Jul 2003
Journal: European Journal of Operational Research
Authors: , ,
Abstract:

We present a big-M method for solving general linear programming problems with a recently developed exterior point simplex algorithm (EPSA). We also provide intuitive motivations to EPSA. We describe major steps in implementing EPSA for large-scale linear programming. Our implementation was carried out under the MATLAB environment. This algorithm seems to be more efficient than the classical primal simplex algorithm (PSA), employing Dantzig's rule. Preliminary computational studies on randomly generated sparse and dense small and medium linear programs support this belief. In particular, EPSA is up to 10 times faster than PSA on medium size linear programs. This translates into corresponding savings in CPU time. Although the computational effort required in each step of EPSA requires more time compared to an iteration step of PSA, the improvement of EPSA comes from the fact that it requires adequately less iterations than PSA. Moreover, as the problem size increases and the problem density decreases, EPSA gets relatively faster.

Reviews

Required fields are marked *. Your email address will not be published.