Back to results

University of Macedonia Economic and Social Sciences

Παράλληλος προγραμματισμός αλγόριθμων για προβλήματα γραμμικού προγραμματισμού

Abstract

dc:description

The 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 × 10

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/14246

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Badr, El-Said. Παράλληλος προγραμματισμός αλγόριθμων για προβλήματα γραμμικού προγραμματισμού. University of Macedonia Economic and Social Sciences, 2006. http://hdl.handle.net/10442/hedi/14246