University of Macedonia Economic and Social Sciences
Hybrid optimization algorithms: implementation on GPU
Abstract
dc:descriptionLinear 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 × 14Rights
dc:rights- Statement dc:rights
-
- BY_ND
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/35245