Computational complexity analysis of linear optimization algorithms
Authors: Βουλγαροπούλου Σοφία 
Published: June 2022

Η ανάλυση της υπολογιστικής πολυπλοκότητας και της απόδοσης αλγορίθμων Γραμμικής Βελτιστοποίησης ήταν πάντα ένας τομέας ιδιαίτερου ενδιαφέροντος, στο πεδίο της Επιχειρησιακής Έρευνας, για την παγκόσμια ερευνητική κοινότητα. Στην παρούσα διδακτορική διατριβή, παρουσιάζονται η έρευνα και όλα τα στοιχεία και αποτελέσματα της ανάλυσης που πραγματοποιήθηκε για την απόδοση του Πρωτεύοντος αλγορίθμου Simplex (Primal Simplex Algorithm, PSA), του Δυϊκού αλγορίθμου Simplex (Dual Simplex Algorithm, DSA), του αλγορίθμου εσωτερικών σημείων (Interior Point Method, IPM) και του αλγορίθμου Simplex εξωτερικών σημείων (Exterior Point Simplex Algorithm, EPSA). Ο κύριος σκοπός της διατριβής είναι η δημιουργία έγκυρων και ακριβών μοντέλων πρόβλεψης για την υπολογιστική απόδοση των παραπάνω αλγορίθμων, καθώς μέχρι σήμερα, έχει παρατηρηθεί σημαντική διαφορά μεταξύ της θεωρητικής πολυπλοκότητας χειρότερης περίπτωσης και της πρακτικής απόδοσης των αλγορίθμων τύπου Simplex. Η ανάλυση διακρίνεται σε τρία βασικά τμήματα, όπως αυτά περιγράφονται παρακάτω. Αρχικά, ερευνάται η υπολογιστική συμπεριφορά του αλγορίθμου EPSA. Για την ανάλυσή του, πραγματοποιήθηκαν υπολογιστικά πειράματα σε συνολικά 6780 αραιά γραμμικά προβλήματα, που δημιουργήθηκαν μέσω γεννήτριας τυχαίων προβλημάτων, αλλά και σε ένα μικρότερο σύνολο από προβλήματα benchmark. Σε αυτό το πρώτο μέρος της έρευνας, έγινε μέτρηση του αριθμού των επαναλήψεων που χρειάστηκε να εκτελέσει ο EPSA για την επίλυση των παραπάνω προβλημάτων, αλλά και του benchmark συνόλου δεδομένων. Ο στόχος ήταν, μέσω της μεθόδου της ανάλυσης παλινδρόμησης, να δημιουργηθούν αντιπροσωπευτικά μοντέλα, που όχι μόνο θα ήταν σημαντικά για την εκτίμηση της απόδοσης του αλγορίθμου, αλλά θα μπορούσαν να σταθούν ως προβλεπτικά μοντέλα για την γενικότερη συμπεριφορά και απόδοση του αλγορίθμου σε νέα προβλήματα. Για κάθε γραμμικό πρόβλημα, λάβαμε υπόψιν διάφορα χαρακτηριστικά, όπως ο αριθμός των περιορισμών και των μεταβλητών του προβλήματος, η αραιότητα αλλά και το μήκος των δεδομένων και η κατάσταση της μήτρας περιορισμών. Είναι αξιοσημείωτο ότι το μοντέλο στο οποίο καταλήξαμε, αποκαλύπτει μια γραμμική συσχέτιση μεταξύ των επαναλήψεων του EPSA και των παραπάνω χαρακτηριστικών.Στη συνέχεια, η ανάλυση επεκτείνεται στο χώρο των μαθηματικών επιλυτών, καθώς μας ενδιαφέρει η δυνατότητα επιλογής του πιο αποδοτικού αλγορίθμου, από πλευράς χρόνου εκτέλεσης, για ένα δεδομένο σύνολο γραμμικών προβλημάτων. Η επιλογή του πιο κατάλληλου και συγκεκριμένα, αποδοτικού αλγορίθμου είναι σημαντική και παράλληλα, απαιτητική διαδικασία σε όλους τους μαθηματικούς επιλυτές γραμμικού προγραμματισμού. Για το σκοπό αυτού του μέρους της ανάλυσης, χρησιμοποιείται ο βελτιστοποιητής CPLEX, ο οποίος υποστηρίζει εκδόσεις των PSA και DSA, καθώς και τον IPM. Εξετάζουμε ένα προβλεπτικό μοντέλο για τον αλγόριθμο IPM, χρησιμοποιώντας τεχνητά νευρωνικά δίκτυα, πάνω σε ένα σύνολο 295 benchmark προβλημάτων γραμμικού προγραμματισμού (Νetlib, Κennington, Mészáros, Mittelmann) για τα οποία μετράται ο χρόνος εκτέλεσης για την επίλυσή τους. Εξετάζονται συγκεκριμένα χαρακτηριστικά των προβλημάτων, όπως ο αριθμός των περιορισμών και των μεταβλητών, τα μη-μηδενικά στοιχεία της μήτρας περιορισμών και του δεξιού μέλους, αλλά και ο βαθμός της μήτρας περιορισμών των προβλημάτων. Στόχος είναι ο εντοπισμός ενός μοντέλου, που θα προβλέπει την απόδοση του αλγορίθμου σε νέα προβλήματα παρόμοιας δομής και θα μπορεί να χρησιμοποιηθεί, πριν την εκτέλεση του αλγορίθμου, για την εκτίμηση του χρόνου εκτέλεσής του. Τα πειραματικά αποτελέσματα δείχνουν καλή προσαρμογή του μοντέλου, τόσο στο σύνολο προβλημάτων εκπαίδευσης (training set) όσο και στο σύνολο προβλημάτων επαλήθευσης (test set), με την τιμή του συντελεστή προσδιορισμού να είναι 78% και 72%, αντίστοιχα.Η έρευνα ολοκληρώνεται με την εξέταση ενός προβλεπτικού μοντέλου, μέσω τεχνητών νευρωνικών δικτύων, για την απόδοση των αλγορίθμων PSA και DSA που υποστηρίζονται στο βελτιστοποιητή CPLEX. Σε αυτό το μέρος της ανάλυσης, χρησιμοποιείται το ίδιο σύνολο προβλημάτων και οι ίδιες μεταβλητές όπως για τον IPM. Τα εξαγόμενα αποτελέσματα αποδεικνύουν ότι ένα μοντέλο παλινδρόμησης, δύσκολα θα μπορούσε να προβλέψει με ακρίβεια το χρόνο εκτέλεσης των αλγορίθμων PSA και DSA. Για να ξεπεραστεί το παραπάνω εμπόδιο, το πρόβλημα αντιμετωπίζεται ως πρόβλημα κατηγοριοποίησης, όπου αντί να υπολογίζεται ο χρόνος εκτέλεσης, υπολογίζεται η κλάση κάτω από την οποία θα κατηγοριοποιηθεί ο χρόνος εκτέλεσης. Τα πειραματικά αποτελέσματα δείχνουν μια καλή εφαρμογή των μοντέλων, τόσο για τον Primal αλλά και για τον Dual, με τιμή ακρίβειας 0.83 και 0.84, αντίστοιχα.Σχετικά με τη δομή του κείμενου της διατριβής, στο πρώτο κεφάλαιο γίνεται μια συνοπτική εισαγωγή στις έννοιες της Επιχειρησιακής Έρευνας, του Γραμμικού Προγραμματισμού και της ανάλυσης της απόδοσης αλγορίθμων, ενώ στη συνέχεια περιγράφονται η συμβολή της διατριβής και η δομή του υπόλοιπου εγγράφου. Στο δεύτερο κεφάλαιο, περιγράφουμε πιο αναλυτικά, τις βασικές έννοιες, την ιστορία και τις εφαρμογές του Γραμμικού Προγραμματισμού, ενώ παραθέτουμε μια σύντομη, αλλά περιεκτική παρουσίαση των αλγορίθμων γραμμικού προγραμματισμού τύπου Simplex, που μελετήθηκαν κατά τη διάρκεια εκπόνησης της παρούσας διατριβής, δηλαδή των PSA, DSA, IPM και EPSA. To κεφάλαιο κλείνει με μία περιγραφή των διαδικασιών που ακολουθούνται για την ανάλυση πολυπλοκότητας και απόδοσης των αλγορίθμων γραμμικού προγραμματισμού και μία επισκόπηση των ερευνών που έχουν γίνει στο παρελθόν. Το τρίτο κεφάλαιο ακολουθεί με αναλυτική περιγραφή των μεθόδων κατασκευής προβλεπτικών μοντέλων που μελετήθηκαν και εφαρμόστηκαν κατά τη διάρκεια της έρευνας για τους στόχους της παρούσας διατριβής. Συγκεκριμένες πληροφορίες δίνονται τόσο για τεχνική της ανάλυσης παλινδρόμησης, όσο και για τις μετρικές που υποστηρίζουν την αξιολόγηση των μοντέλων παλινδρόμησης. Επιπρόσθετα, περιγράφεται η λειτουργία των τεχνητών νευρωνικών δικτύων και η γενικότερη διαδικασία εκπαίδευσής τους. Στο τέταρτο κεφάλαιο, παρουσιάζονται λεπτομερώς όλα τα σύνολα δεδομένων που αναλύσαμε σε όλα τα στάδια της έρευνάς μας, αλλά και τα υπολογιστικά περιβάλλοντα που αξιοποιήθηκαν, στα πλαίσια εκπόνησης της παρούσας διατριβής. Το πέμπτο κεφάλαιο αποτελείται από την λεπτομερή παρουσίαση της ανάλυσης και των αντίστοιχων αποτελεσμάτων των προβλεπτικών μοντέλων στα οποία καταλήξαμε. Τα μοντέλα περιγράφονται για κάθε αλγόριθμο ξεχωριστά και συνοδεύονται από τα αντίστοιχα αποτελέσματα ελέγχου και εγκυρότητάς τους. Τέλος, το έκτο κεφάλαιο συνοψίζει τα συμπεράσματα της παρούσας διατριβής και συνθέτει τα ευρήματα για τους αλγορίθμους που εξετάστηκαν. Επίσης, περιλαμβάνει ιδέες και προτάσεις για μελλοντική έρευνα και επιπλέον ανάλυση.