Πανεπιστήμιο Μακεδονίας
A non-monotonic infleasible interior-exterior point algorithm for linear programming
Abstract
dc:descriptionThe vast majority of Linear Programming algorithms restrict the use of any vertex as starting basis, into being either primal feasible, dual feasible, or even both (Primal – Dual Two path pivoting algorithms). A reasonably large amount of research has been conducted the latest decades to relax these limitations. Exterior Point algorithms, originally designed from Paparrizos K. differ versus the traditional pivoting algorithms in the sense that they construct primal infeasible bases as well along with the feasible ones. It looks ambiguous whether it would be impractical to combine exterior with interior point methods. This paper presents a variant of the exterior point algorithmic family for the linear problem, iEPSA, in an attempt to shed light upon this ambiguity. It can be considered as a generalization of this type of algorithms, since it does not suffer from feasibility criteria on the starting vertex and in parallel it was educed by two already known LP algorithms. To expunge an algorithm though from these restrictions, translates to a partially non-monotonic design, which is rather than a facile task. It embodies interior, primal and dual ingredients, all together mixed into a hybrid algorithm. We compare its practical effectiveness against the IPM (Interior Point Method) of MOSEK optimization package implemented for the computational environment of MATLAB-R2012b. The results extrapolate a significant implication that in some cases, a combination of interior-exterior methods is considerably more efficient. This comes to gainsay with the up-to-date information we have about the state-of-the-art LP solvers.
Degree
thesis:*- Grantor dc:publisher
- Πανεπιστήμιο Μακεδονίας
- Year dc:date
- 2013
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Triantafyllidis, Charalampos
- Τριανταφυλλίδης, Χαράλαμπος
Subjects
dc:subject × 14- Γραμμικός προγραμματισμός
- Αλγόριθμοι εξωτερικών σημείων
- Υπολογιστική επιχειρησιακή έρευνα
- Linear programming
- Exterior-point algorithms
- Computational operations research
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
dc:rights- Statement dc:rights
-
- BY_NC_ND
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/36838