Please use this identifier to cite or link to this item:
https://ruomo.lib.uom.gr/handle/7000/541
Title: | A parallel implementation of an exterior point algorithm for linear programming problems |
Authors: | Ploskas, Nikolaos Samaras, Nikolaos Sifaleras, Angelo |
Type: | Conference Paper |
Subjects: | FRASCATI::Natural sciences::Mathematics::Applied Mathematics FRASCATI::Natural sciences::Computer and information sciences |
Keywords: | Computational Study Exterior Point Simplex type Algorithm Linear Programming Parallel Programming |
Issue Date: | 3-Sep-2009 |
Volume Title: | Proceedings of the 9th Balkan Conference on Operational Research (BALCOR 2009) |
Abstract: | The simplex method is perhaps the most widely used method for solving linear programming (LP) problems. The computation time of simplex type algorithms depends on the basis inverse that occurs in each iteration. Parallelizing simplex type algorithms is one of the most challenging problems. The aim of this paper is to present a parallel implementation of the primal exterior point simplex algorithm. In this approach the basis inverse is computed in parallel. The matrix that holds the basis is distributed among different workers and the computation is performed faster in large-scale LP problems. Apart from the parallel implementation, this paper presents a computational study that shows the speedup among the serial and parallel version in large-scale randomly generated full dense LP problems. |
URI: | https://ruomo.lib.uom.gr/handle/7000/541 |
Appears in Collections: | Department of Applied Informatics |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
A_parallel_implementation_of_an_exterior_point_algorithm_for_linear_programming_problems.pdf | 103,76 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.