Computational complexity analysis of linear optimization algorithms

Abstract

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. Specifically, 6780 linear problems have been randomly generated, in order to formulate a respectable amount of experiments. This first part of our study consists of the measurement of the number of iterations that EPSA needs for the solution of the above mentioned problems and benchmark dataset. Our purpose is to form representative regression models, which would be significant for the evaluation of the algorithm’s efficiency and could act as predictive models for the algorithm’s performance. From each linear problem, we have taken several characteristics into account, such as the number of constraints and variables, the sparsity and bit length, and the condition of the constraint matrix. It is remarkable that the formulated model for the randomly generated problems reveals a linear relation between the number of EPSA iterations and the above mentioned characteristics. Next, we extend our analysis, being concerned about the ability to choose the most efficient algorithm, in terms of execution time, for a given set of linear programming problems. Algorithm selection has been a significant, but at the same time, challenging process in all linear programming solvers. For the purpose of this part of our study, we utilize CPLEX Optimizer, which supports Primal and Dual variants of the Simplex algorithm and the Interior Point Method (IPM). We examine a performance prediction model using artificial neural networks for the CPLEX’s Interior Point Method on a set of 295 benchmark linear programming problems (Netlib, Kennington, Mészáros, Mittelmann) and measure the execution time needed for their solution. Specific characteristics of the linear programming problems are examined, such as the number of constraints and variables, the nonzero elements of the constraint matrix and the right-hand side, and the rank of the constraint matrix of the linear programming problems. Our purpose is to identify a model, which could be used for prediction of the algorithm’s efficiency on linear programming problems of similar structure. This model can be used prior to the execution of the interior point method in order to estimate its execution time. Experimental results show a good fit of our model both on the training and test set, with the coefficient of determination value at 78% and 72%, respectively. The current study is concluded by examining a prediction model using artificial neural networks for the performance of CPLEX’s Primal and Dual Simplex algorithms on the same dataset and with the same variables as in IPM. The extracted results prove that a regression model cannot predict accurately the execution time of CPLEX’s Primal and Dual Simplex algorithms. To overcome this issue, we treat the problem as a classification problem. Instead of estimating the execution time, our models estimate the class under which the execution time will fall. Experimental results show a good performance of the models both for Primal and Dual Simple algorithms, with an accuracy score of 0.83 and 0.84, respectively.

Η ανάλυση της υπολογιστικής πολυπλοκότητας και της απόδοσης αλγορίθμων Γραμμικής Βελτιστοποίησης ήταν πάντα ένας τομέας ιδιαίτερου ενδιαφέροντος, στο πεδίο της Επιχειρησιακής Έρευνας, για την παγκόσμια ερευνητική κοινότητα. Στην παρούσα διδακτορική διατριβή, παρουσιάζονται η έρευνα και όλα τα στοιχεία και αποτελέσματα της ανάλυσης που πραγματοποιήθηκε για την απόδοση του Πρωτεύοντος αλγορίθμου 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 κεφάλαιο κλείνει με μία περιγραφή των διαδικασιών που ακολουθούνται για την ανάλυση πολυπλοκότητας και απόδοσης των αλγορίθμων γραμμικού προγραμματισμού και μία επισκόπηση των ερευνών που έχουν γίνει στο παρελθόν. Το τρίτο κεφάλαιο ακολουθεί με αναλυτική περιγραφή των μεθόδων κατασκευής προβλεπτικών μοντέλων που μελετήθηκαν και εφαρμόστηκαν κατά τη διάρκεια της έρευνας για τους στόχους της παρούσας διατριβής. Συγκεκριμένες πληροφορίες δίνονται τόσο για τεχνική της ανάλυσης παλινδρόμησης, όσο και για τις μετρικές που υποστηρίζουν την αξιολόγηση των μοντέλων παλινδρόμησης. Επιπρόσθετα, περιγράφεται η λειτουργία των τεχνητών νευρωνικών δικτύων και η γενικότερη διαδικασία εκπαίδευσής τους. Στο τέταρτο κεφάλαιο, παρουσιάζονται λεπτομερώς όλα τα σύνολα δεδομένων που αναλύσαμε σε όλα τα στάδια της έρευνάς μας, αλλά και τα υπολογιστικά περιβάλλοντα που αξιοποιήθηκαν, στα πλαίσια εκπόνησης της παρούσας διατριβής. Το πέμπτο κεφάλαιο αποτελείται από την λεπτομερή παρουσίαση της ανάλυσης και των αντίστοιχων αποτελεσμάτων των προβλεπτικών μοντέλων στα οποία καταλήξαμε. Τα μοντέλα περιγράφονται για κάθε αλγόριθμο ξεχωριστά και συνοδεύονται από τα αντίστοιχα αποτελέσματα ελέγχου και εγκυρότητάς τους. Τέλος, το έκτο κεφάλαιο συνοψίζει τα συμπεράσματα της παρούσας διατριβής και συνθέτει τα ευρήματα για τους αλγορίθμους που εξετάστηκαν. Επίσης, περιλαμβάνει ιδέες και προτάσεις για μελλοντική έρευνα και επιπλέον ανάλυση.