๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Investigating the sparse simplex algorithm on a distributed memory multiprocessor

โœ Scribed by I. Maros; G. Mitra


Book ID
104304796
Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
140 KB
Volume
26
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

โœฆ Synopsis


There is a sustained interest in improving the computational performance of the sparse simplex (SSX) method for linear programs. Although there have been some investigations covering SSX on parallel computing platforms the performance results have not been particularly encouraging. While it is possible to analyze and understand the lack of success of SSX on parallel platforms we have found a set of beneยฎts (alternative to performance enhancement only) that can be obtained by studying the behaviour of SSX on parallel platforms. In this paper we introduce a cooperating distributed processing algorithm which is a novel implementation of the SSX. Our investigation of this algorithm shows how the distributed parallel architecture is an ideal environment for studying the potentials of the serial SSX. Interestingly, it sheds new light on some ways the performance of SSX can be improved. We give account of our ยฎndings with some mixed pricing strategies. We point out, that our distributed algorithm also can serve as an extremely robustsolver that may be used to a great advantage in case of numerically dicult problems and for those problems for which there is no a priori knowledge of best SSX strategies.


๐Ÿ“œ SIMILAR VOLUMES