Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων
Authors: Σαμαράς Νικόλαος 
Published: August 2021

Ο Γραμμικός Προγραμματισμός ασχολείται με τη βελτιστοποίηση (ελαχιστοποίηση ή μεγιστοποίηση) μιας γραμμικής συνάρτησης κάτω από ορισμένους γραμμικούς (ισοτικούς ή ανισοτικούς) περιορισμούς. Από την ανακάλυψη του αλγορίθμου simplex, το 1947, από τον Dantzig μέχρι σήμερα έχει συντελεστεί μεγάλη πρόοδος στην επιστήμη του Μαθηματικού Προγραμματισμού. Από τη στιγμή που αποδείχτηκε ότι η πολυπλοκότητα χειρότερης του αλγορίθμου simplex είναι εκθετική, το ενδιαφέρον των ερευνητών στράφηκε στη δημιουργία αλγορίθμων πολυωνυμικού χρόνου και στην επίλυση γραμμικών προβλημάτων μεγάλης κλίμακας. Στις αρχές της δεκαετίας του ’90 εμφανίστηκε μια νέα κλάση αλγορίθμων τύπου simplex στη διεθνή βιβλιογραφία. Οι αλγόριθμοι αυτής της κλάσης ονομάζονται αλγόριθμοι εξωτερικών σημείων ή αλγόριθμοι δύο δρόμων. Η πρώτη επιστημονική εργασία στην οποία παρουσιάζεται ένας αλγόριθμος εξωτερικών σημείων δημοσιεύτηκε το 1991 από τον Paparrizos. Ο πρωτεύων αλγόριθμος εξωτερικών σημείων έχει δύο μεγάλα υπολογιστικά μειονεκτήματα. Αυτά είναι:1.Είναι δύσκολη η κατασκευή “καλών” κατευθύνσεων. Οι δύο δρόμοι εξαρτώνται από την αρχική εφικτή κατεύθυνση και από την αρχική εφικτή κορυφή.2.Δεν υπάρχει γνωστός τρόπος μετακίνησης στο εσωτερικό της εφικτής περιοχής. Η μετακίνηση αυτή επιτυγχάνει την εύρεση υπολογιστικά “καλών αρχικών κατευθύνσεων”.Ένας τρόπος αποφυγής των προηγουμένων υπολογιστικών μειονεκτημάτων είναι η μετατροπή του εξωτερικού δρόμου του αλγορίθμου εξωτερικών σημείων σε έναν δυϊκά εφικτό δρόμο simplex. Στην διατριβή αυτή παρουσιάζεται μια υπολογιστική βελτίωση του συνοριακού πρωτεύοντος δυϊκού αλγορίθμου δύο δρόμων τύπου simplex που ανακαλύφθηκε από τον Paparrizos. Συγκεκριμένα, ο νέος αλγόριθμος που κατασκευάστηκε μετακινείται στο εσωτερικό της εφικτής περιοχής και δεν παραμένει στο σύνορο της. Η μετακίνηση στο εσωτερικό της εφικτής περιοχής έχει ως αποτέλεσμα την αποφυγή των φαινομένων της στασιμότητας (stalling) και της κύκλωσης (cycling).Για να προσδιοριστεί η πρακτική αποτελεσματικότητα του αλγορίθμου πραγματοποιήθηκαν εκτεταμένες υπολογιστικές μελέτες. Συγκεκριμένα, πραγματοποιήθηκαν τρεις διαφορετικές υπολογιστικές μελέτες. Για την επίλυση των γραμμικών προβλημάτων μεγάλης κλίμακας των υπολογιστικών μελετών εφαρμόστηκαν και χρησιμοποιήθηκαν τεχνικές όπως, προλυτικές διαδικασίες, τεχνικές κλιμάκωσης, ανοχές και όποτε χρειάζονταν υπολογισμός της αντίστροφης της βάσης από την αρχή. Οι υπολογιστικές μελέτες αναφέρονται σε τυχαία αραιά γραμμικά προβλήματα των οποίων η αρχική βασική λύση είναι δυϊκά εφικτή, σε τυχαία αραιά γραμμικά προβλήματα των οποίων η αρχική βασική λύση δεν είναι ούτε αρχικά ούτε δυϊκά εφικτή και σε μετροπρογράμματα (www.netlib.org).Τα υπολογιστικά αποτελέσματα είναι ενθαρρυντικά για τον νέο αλγόριθμο. Συγκεκριμένα, σε τυχαία αραιά γραμμικά προβλήματα των οποίων η αρχική βασική λύση δεν είναι ούτε αρχικά ούτε δυϊκά εφικτή διάστασης 1200x1200 και με πυκνότητες 2.5%, 5% και 10%, ο νέος αλγόριθμος είναι 169, 126 και 128 φορές ταχύτερος του κλασικού αλγορίθμου simplex και 1.16, 1.10 και 1.15 φορές ταχύτερος του πρωτεύοντος δυϊκού συνοριακού αλγορίθμου δύο δρόμων τύπου simplex. Η καλυτέρευση αυτή μεταφράζεται σε CPU χρόνο ως εξής. Ο νέος αλγόριθμος είναι 108, 97 και 98 φορές ταχύτερος του κλασικού αλγορίθμου simplex και 1.14, 1.08 και 1.17 φορές ταχύτερος του πρωτεύοντος δυϊκού συνοριακού αλγορίθμου δύο δρόμων τύπου simplex αντίστοιχα.