University of Macedonia Economic and Social Sciences
Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων
Abstract
dc:descriptionLinear 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- Γραμμικός προγραμματισμός
- Αλγόριθμοι τύπου Simplex
- Αλγόριθμοι εξωτερικών σημείων
- Υπολογιστική μελέτη
- Linear programming
- Simplex type algorithms
- Exterior point algorithms
- Computational study
- Φυσικές Επιστήμες
- Μαθηματικά
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Mathematics
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/30472