Please use this identifier to cite or link to this item:
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.
Appears in Collections:Department of Applied Informatics

Files in This Item:
File Description SizeFormat 
A_parallel_implementation_of_an_exterior_point_algorithm_for_linear_programming_problems.pdf103,76 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.