Back to search

University of Macedonia Economic and Social Sciences

Hybrid optimization algorithms: implementation on GPU

Abstract

dc:description

Linear Programming (LP) is a significant area in the field of operations research. The simplex algorithm is one of the top ten algorithms with the greatest influence in the 20th century and the most widely used method for solving LP problems. The main aim of this thesis is to investigate the computational aspects of two simplex type algorithms: (i) the revised simplex algorithm, and (ii) a primal-dual exterior point simplex algorithm. Furthermore, Graphical Processing Units (GPUs) have gained a lot of popularity and have been applied to LP algorithms. Hence, the simplex type algorithms and the different methods in these algorithms are implemented both as CPU- and GPU-based implementations.Preconditioning techniques are important in solving linear problems, as they improve their computational properties. Scaling is the most widely used preconditioning technique in linear optimization algorithms and is used to reduce the condition number of the constraint matrix, improve the numerical behavior of the algorithms and reduce the number of iterations required to solve linear problems. Ten existing scaling techniques are reviewed and computationally compared. Moreover, we also propose a GPU-based implementation of these techniques. Computational results show that on average the speedup gained from the GPU-based implementations of all scaling methods is about 7x. The choice of the pivot element at each iteration is one of the most critical step in simplex type algorithms. Good choices of the entering variable can lead to fast convergence to the optimal solution, while poor choices lead to more iterations and worst execution times or even no solutions of the LPs. Six existing pivoting rules for the revised simplex algorithm are implemented. Furthermore, we also propose a GPU-based implementation of these rules. Computational results show that only the Steepest Edge rule can be implemented efficiently on a GPU.The computation of the basis inverse is the most time-consuming step in simplex type algorithms. This inverse does not have to be computed from scratch at any iteration, but updating schemes can be applied to accelerate this calculation. We review and implement five basis updating schemes. Then, we propose an implementation of two updating schemes on a CPU-GPU system. Computational results show that the Modification of the Product Form of the Inverse method is fastest than the other basis updating methods both on a CPU and on a GPU and its’ speedup is up to 19 for the time of the basis inverse and 5 for the total time.Finally, we propose two efficient GPU-based implementations of the revised simplex algorithm and a primal-dual exterior point simplex algorithm. Both GPU-based algorithms have been implemented in MATLAB using MATLABs Parallel Computing Toolbox. Computational results on randomly generated optimal sparse and dense linear programming problems are also presented. The results show that the proposed GPU-based implementations outperform MATLAB's interior point method.

Degree

thesis:*
Grantor dc:publisher
University of Macedonia Economic and Social Sciences
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Ploskas, Nikolaos
  • Πλόσκας, Νικόλαος

Subjects

dc:subject × 14

Rights

dc:rights
Statement dc:rights
  • BY_ND
Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/35245

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

Ploskas, Nikolaos; Πλόσκας, Νικόλαος. Hybrid optimization algorithms: implementation on GPU. University of Macedonia Economic and Social Sciences, 2014. http://hdl.handle.net/10442/hedi/35245