Back to results

University of Macedonia Economic and Social Sciences

Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων

Abstract

dc:description

Linear Programming deals with the optimization (minimization or maximization) of an objective function under certain linear (equality or inequality) constraints. Great progress has been made in mathematical programming since the introduction of the simplex algorithm in 1947 by Dantzig. Researchers' interest turned to polynomial complexity algorithms in order to solve large-scale linear problems since the moment that the worst-case complexity of the simplex algorithm proved to be exponential. In the early 1990s, a new class of simplex type algorithms appeared in the international bibliography. The algorithms of this class are called exterior point or two-path algorithms. The first paper, in which an exterior point algorithm was presented, published in 1991 by Paparrizos. The primal exterior point algorithm has two main computational drawbacks: 1.It is difficult to construct "good moving directions". The two paths depend on the initial feasible direction and the initial feasible vertex. 2.There is no known way of moving into the interior of the feasible region. This movement achieves the search for computationally good directions.Forcing the exterior path of an exterior point algorithm to become a dual feasible simplex path results in an algorithm free of the above-mentioned computational drawbacks.In this thesis, a computational improvement of the primal dual two-path simplex algorithm proposed by Paparrizos is presented. More specifically, the new algorithm that was implemented moves in the interior of the feasible region and not in its' frontier. Moving to the interior of the feasible region results in an algorithm free of the stalling and cycling phenomena. Extensive computations studies were conducted in order to study the practical effectiveness of the algorithm. More specifically, three different computational studies were conducted. Presolve techniques, scaling techniques, tolerances and explicit inverse of the basis when needed were applied in order to solve large-scale linear problems. In the computational studies, the problems that were used are randomly generated sparse linear problems with a dual feasible initial basic solution, randomly generated sparse linear problems with an initial basic solution that is neither primal nor dual feasible and benchmark linear problems (www.netlib.org). The computational results for the new algorithm are encouraging. More specifically, in randomly generated sparse linear problems of size 1200x1200 with an initial basic solution that is neither primal nor dual feasible and density 2.5%, 5% and 10%, the new algorithm is 169, 126 and 128 times faster than the original simplex algorithm and 1.16, 1.10 and 1.15 times faster than the primal dual two-path simplex algorithm, respectively. This improvement is translated to CPU time as follows. The new algorithm is 108, 97 and 98 times faster than the original simplex algorithm and 1.14, 1.08 and 1.17 times faster than the primal dual two-path simplex algorithm, respectively.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Samaras, Nikolaos
  • Σαμαράς, Νικόλαος

Subjects

dc:subject × 14

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/30472

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

Samaras, Nikolaos; Σαμαράς, Νικόλαος. Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων. University of Macedonia Economic and Social Sciences, 2001. http://hdl.handle.net/10442/hedi/30472