University of Macedonia Economic and Social Sciences
Παράλληλος προγραμματισμός αλγόριθμων για προβλήματα γραμμικού προγραμματισμού
Abstract
dc:descriptionThe Simplex Method, the most popular method for solving Linear Programs (LPs), has two major variants. They are the revised method and the standard, or full tableau method. Today, virtually all serious implementations are of the revised method because it is more efficient for sparse LPs which are the most common. However, the full tableau method has advantages as well. First, the full tableau can be very effective for dense problems. Second, a full tableau method can easily and effectively be extended to a coarse grained distributed algorithm. While dense problems are uncommon in general, they occur frequently in some important applications such as digital filter design, text categorization, image processing and relaxations of scheduling problems. We implement two full tableau algorithms. The first, a serial implementation, is effective for small to moderately sized dense problems. The second, a simple extension of the first, is a distributed algorithm. We implement an algorithm which converts MPS format to LP format and we convert a subset of benchmark problems from NETLIB. We present an analysis of two well-known updating schemes for basis inverse: (i) The Product Form of the Inverse ( PFI ) and (ii) A Modification of the Product Form Inverse ( MPFI ) and incorporate it with EPSA. Computation results with a subset of benchmark problems from NETLIB indicate that the Modification of the Product Form of the Inverse is 1.60 times faster than the product form of the inverse in most problems. We implement the exterior point simplex. 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 linear programs support this belief. 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.
Degree
thesis:*- Grantor dc:publisher
- University of Macedonia Economic and Social Sciences
- Year dc:date
- 2006
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Badr, El-Said
Subjects
dc:subject × 10Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/14246