Πανεπιστήμιο Μακεδονίας
Design and development of a hybrid mathematical programming algorithm
Abstract
dc:descriptionOne of the most significant and well-studied optimization problems is the Linear Programming problem (LP). LP consists of optimizing, (minimizing or maximizing) a linear function over a certain domain. The domain is given by a set of linear constraints. The presence of effective presolve techniques is of great importance for every linear programming solver. The main goal of the presolve session is to reduce the problem's size and to determine whether the problem is unbounded or infeasible. Computational results with a set of optimal benchmark problems from NETLIB are also presented. Finally, simplex algorithm has been used in order to solve benchmarks before and after a new proposed presolve technique has been performed to LPs.Moreover, an experimental investigation of a variation of Primal-Dual Exterior Point Simplex Algorithm (PDEPSA) is presented and it is called Primal-Dual Interior Point Simplex Algorithm (PDIPSA). In order to gain an insight into the practical behavior of the proposed algorithm, we have performed some computational experiments. Our computational results demonstrate that PDIPSA is faster comparable with simplex algorithm and primal exterior point algorithm.The main aim of this thesis is to present a hybrid algorithm which combines the strengths of Interior Point Methods (IPMs) and Exterior Point Simplex Algorithms (EPSAs). The hybrid algorithm takes full advantage of IPM at the first iterations which lead to significant enhancement of the objective function's value. The hybrid algorithm uses the Primal Dual Interior Point Simplex Algorithm (PDIPSA) which is a variation of EPSAs and computes a direction to the feasible region according to the interior point that was calculated by IPM. Furthermore, a computational study is presented with experiments over the Netlib set (optimal, Kennington and infeasible LPs) and the Misc section of Meszaros collection.
Degree
thesis:*- Grantor dc:publisher
- Πανεπιστήμιο Μακεδονίας
- Year dc:date
- 2019
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Glavelis, Themistoklis
- Γλαβέλης, Θεμιστοκλής
Subjects
dc:subject × 9Rights
dc:rights- Statement dc:rights
-
- BY
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/46141