Ανάλυση υπολογιστικής πολυπολοκότητας αλγορίθμων γραμμικής βελτιστοποίησης

Περίληψη

Η ανάλυση της υπολογιστικής πολυπλοκότητας και της απόδοσης αλγορίθμων Γραμμικής Βελτιστοποίησης ήταν πάντα ένας τομέας ιδιαίτερου ενδιαφέροντος, στο πεδίο της Επιχειρησιακής Έρευνας, για την παγκόσμια ερευνητική κοινότητα. Στην παρούσα διδακτορική διατριβή, παρουσιάζονται η έρευνα και όλα τα στοιχεία και αποτελέσματα της ανάλυσης που πραγματοποιήθηκε για την απόδοση του Πρωτεύοντος αλγορίθμου Simplex (Primal Simplex Algorithm, PSA), του Δυϊκού αλγορίθμου Simplex (Dual Simplex Algorithm, DSA), του αλγορίθμου εσωτερικών σημείων (Interior Point Method, IPM) και του αλγορίθμου Simplex εξωτερικών σημείων (Exterior Point Simplex Algorithm, EPSA). Ο κύριος σκοπός της διατριβής είναι η δημιουργία έγκυρων και ακριβών μοντέλων πρόβλεψης για την υπολογιστική απόδοση των παραπάνω αλγορίθμων, καθώς μέχρι σήμερα, έχει παρατηρηθεί σημαντική διαφορά μεταξύ της θεωρητικής πολυπλοκότητας χειρότερης περίπτωσης και της πρακτικής απόδοσης των αλγορίθμων τύπου Simplex. Η ανάλυση διακρίνεται σε τρία βασικ ...
περισσότερα

Περίληψη σε άλλη γλώσσα

Computational complexity and performance analysis in Linear Optimization algorithms have always been topics of particular interest among the Operational Research community. In the current thesis, we are presenting all aspects and analysis results of our study on the performance of the Exterior Point Simplex algorithm, the Interior Point Method, and the Primal and Dual Simplex algorithms. Our objective is to generate valid and accurate prediction models for the computational performance of these algorithms. Our analysis is separated in three main parts, as described below. First, we investigate the computational behavior of the Exterior Point Simplex algorithm (EPSA). Up until now, a significant difference has been observed between the theoretical worst case complexity and practical performance of simplex-type algorithms. To appropriately examine the latter, computational tests have been carried out on randomly generated sparse linear problems and on a small set of benchmark problems. S ...
περισσότερα

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/51709
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/51709
ND
51709
Εναλλακτικός τίτλος
Computational complexity analysis of linear optimization algorithms
Συγγραφέας
Βουλγαροπούλου, Σοφία του Παντελής
Ημερομηνία
2022
Ίδρυμα
Πανεπιστήμιο Μακεδονίας. Σχολή Επιστημών Πληροφορίας. Τμήμα Εφαρμοσμένης Πληροφορικής
Εξεταστική επιτροπή
Samaras Nikolaos
Hristu - Varsakelis Dimitrios
Sifaleras Angelos
Evangelidis Georgios
Giannoutakis Konstantinos
Ploskas Nikolaos
Stergiou Kostas
Επιστημονικό πεδίο
Φυσικές ΕπιστήμεςΕπιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική ➨ Επιστήμη ηλεκτρονικών υπολογιστών
Λέξεις-κλειδιά
Ανάλυση υπολογιστικής πολυπλοκότητας; Αλγόριθμοι γραμμικής βελτιστοποίησης; Μοντέλα πρόβλεψης; Ανάλυση παλινδρόμησης; Τεχνητά νευρωνικά δίκτυα; Πρωτεύων simplex; Simplex εξωτερικών σημείων; Μέθοδος εσωτερικού σημείου; Δυικός simplex; Μοντέλα χρονισμού; Πρακτική απόδοση; Ανάλυση απόδοσης
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
εικ., πιν., γραφ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.