Back to search

Πανεπιστήμιο Μακεδονίας

A non-monotonic infleasible interior-exterior point algorithm for linear programming

Abstract

dc:description

The 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

Rights

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

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/36838

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

Triantafyllidis, Charalampos; Τριανταφυλλίδης, Χαράλαμπος. A non-monotonic infleasible interior-exterior point algorithm for linear programming. Πανεπιστήμιο Μακεδονίας, 2013. http://hdl.handle.net/10442/hedi/36838