DISTRIBUTED NESTED DECOMPOSITION OF STAIRCASE LINEAR-PROGRAMS

Citation
Jk. Ho et Rp. Sundarraj, DISTRIBUTED NESTED DECOMPOSITION OF STAIRCASE LINEAR-PROGRAMS, ACM transactions on mathematical software, 23(2), 1997, pp. 148-173
Citations number
24
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Sciences",Mathematics,"Computer Science Software Graphycs Programming",Mathematics
ISSN journal
0098-3500
Volume
23
Issue
2
Year of publication
1997
Pages
148 - 173
Database
ISI
SICI code
0098-3500(1997)23:2<148:DNDOSL>2.0.ZU;2-3
Abstract
This article considers the application of a primal nested-decompositio n method to solve staircase linear programs (SLPs) on distributed-memo ry, multiple-instruction-multiple-data computers. Due to the coupling that exists among the stages of an SLP, a standard parallel-decomposit ion algorithm for these problems would allow only a subset of the subp roblem processes to overlap with one another at any give time. We prop ose algorithms that seek to increase the amount of overlap among the p rocesses as well as utilize idle time beneficially. Computational resu lts testing the effectiveness of our algorithms are reported, using a standard set of test problems.