Hybrid optimization algorithms: implementation on GPU

Abstract

Linear Programming (LP) is a significant area in the field of operations research. The simplex algorithm is one of the top ten algorithms with the greatest influence in the 20th century and the most widely used method for solving LP problems. The main aim of this thesis is to investigate the computational aspects of two simplex type algorithms: (i) the revised simplex algorithm, and (ii) a primal-dual exterior point simplex algorithm. Furthermore, Graphical Processing Units (GPUs) have gained a lot of popularity and have been applied to LP algorithms. Hence, the simplex type algorithms and the different methods in these algorithms are implemented both as CPU- and GPU-based implementations.Preconditioning techniques are important in solving linear problems, as they improve their computational properties. Scaling is the most widely used preconditioning technique in linear optimization algorithms and is used to reduce the condition number of the constraint matrix, improve the numerical behavior of the algorithms and reduce the number of iterations required to solve linear problems. Ten existing scaling techniques are reviewed and computationally compared. Moreover, we also propose a GPU-based implementation of these techniques. Computational results show that on average the speedup gained from the GPU-based implementations of all scaling methods is about 7x. The choice of the pivot element at each iteration is one of the most critical step in simplex type algorithms. Good choices of the entering variable can lead to fast convergence to the optimal solution, while poor choices lead to more iterations and worst execution times or even no solutions of the LPs. Six existing pivoting rules for the revised simplex algorithm are implemented. Furthermore, we also propose a GPU-based implementation of these rules. Computational results show that only the Steepest Edge rule can be implemented efficiently on a GPU.The computation of the basis inverse is the most time-consuming step in simplex type algorithms. This inverse does not have to be computed from scratch at any iteration, but updating schemes can be applied to accelerate this calculation. We review and implement five basis updating schemes. Then, we propose an implementation of two updating schemes on a CPU-GPU system. Computational results show that the Modification of the Product Form of the Inverse method is fastest than the other basis updating methods both on a CPU and on a GPU and its’ speedup is up to 19 for the time of the basis inverse and 5 for the total time.Finally, we propose two efficient GPU-based implementations of the revised simplex algorithm and a primal-dual exterior point simplex algorithm. Both GPU-based algorithms have been implemented in MATLAB using MATLABs Parallel Computing Toolbox. Computational results on randomly generated optimal sparse and dense linear programming problems are also presented. The results show that the proposed GPU-based implementations outperform MATLAB's interior point method.

Ο Γραμμικός Προγραμματισμός (ΓΠ) είναι ένα σημαντικός τομέας της επιχειρησιακής έρευνας. Ο αλγόριθμος simplex είναι ένας από τους δέκα αλγόριθμους με τη μεγαλύτερη επιρροή στον 20ο αιώνα και η πιο ευρέως χρησιμοποιούμενη μέθοδος για την επίλυση γραμμικών προβλημάτων. Ο κύριος στόχος της διατριβής αυτής είναι η μελέτη της υπολογιστικής συμπεριφοράς δύο αλγορίθμων τύπου simplex: (i) του αναθεωρημένου αλγόριθμου simplex, και (ii) του πρωτεύοντα – δυϊκού αλγόριθμου simplex εξωτερικών σημείων. Επίσης, οι Κάρτες Γραφικών (Graphical Processing Units – GPUs) έχουν γίνει δημοφιλείς και έχουν εφαρμοστεί για την επίλυση γραμμικών προβλημάτων. Οι αλγόριθμοι τύπου simplex και οι διαφορετικές μέθοδοι στους αλγορίθμους αυτούς υλοποιούνται τόσο στη CPU όσο και στη GPU.Οι preconditioning τεχνικές είναι σημαντικές στην επίλυση γραμμικών προβλημάτων, καθώς βελτιώνουν την υπολογιστική συμπεριφορά των αλγορίθμων. Η κλιμάκωση είναι η πιο ευρέως διαδεδομένη preconditioning τεχνική στους αλγόριθμους γραμμικού προγραμματισμού και χρησιμοποιείται για τη μείωση του βαθμού κατάστασης του πίνακα των περιορισμών, για τη βελτίωση της υπολογιστικής συμπεριφοράς των αλγορίθμων και για τη μείωση του αριθμού των επαναλήψεων που απαιτούνται για την επίλυση των γραμμικών προβλημάτων. Δέκα τεχνικές κλιμάκωσης μελετώνται και συγκρίνονται υπολογιστικά. Επίσης, προτείνουμε υλοποίησης των μεθόδων αυτών σε GPUs. Τα υπολογιστικά αποτελέσματα δείχνουν ότι υπάρχει μία επιτάχυνση της τάξης του 7 για όλες τις τεχνικές κλιμάκωσης που υλοποιήθηκαν σε GPUs.Η επιλογή του στοιχείου περιστροφής σε κάθε επανάληψη είναι ένα σημαντικό βήμα στους αλγορίθμους τύπου simplex. Καλές επιλογές της εισερχόμενης μεταβλητής μπορεί να οδηγήσουν σε πιο γρήγορη εύρεση της βέλτιστης λύσης, ενώ κακές επιλογές οδηγούν σε περισσότερες επαναλήψεις και χειρότερους χρόνους εκτέλεσης ή ακόμα και με εύρεση της βέλτιστης λύσης του γραμμικού προβλήματος. Έξι κανόνες περιστροφής υλοποιήθηκαν για τον αναθεωρημένο αλγόριθμο simplex. Επίσης, προτείνουμε υλοποιήσεις των κανόνων αυτών σε GPUs. Τα υπολογιστικά αποτελέσματα δείχνουν ότι μόνο η μέθοδος Steepest Edge Rule είναι κατάλληλη για υλοποίηση σε GPUs.Ο υπολογισμός της αντιστρόφου της βάσης είναι το πιο χρονοβόρο βήμα στους αλγορίθμους τύπου simplex. Το βήμα αυτό δε χρειάζεται να γίνεται εξαρχής σε κάθε επανάληψη, αλλά σχήματα ανανέωσης της βάσης μπορούν να εφαρμοστούν για την επιτάχυνση της διαδικασίας. Μελετούμε και υλοποιούμε πέντε μεθόδους υπολογισμού τη αντιστρόφου. Στη συνέχεια, προτείνουμε υλοποίησης σε GPUs για δύο από αυτές τις μεθόδους. Τα υπολογιστικά αποτελέσματα δείχνουν ότι η μέθοδος Modification of the Product Form of the Inverse είναι ταχύτερη των υπόλοιπων μεθόδων τόσο στη CPU όσο και στη GPU και η επιτάχυνση που επιτυγχάνεται είναι 19 για το βήμα της ανανέωσης της βάσης και 5 για το συνολικό χρόνο του αλγορίθμου.Τέλος, προτείνουμε δύο αποδοτικές υλοποιήσεις σε GPUs του αναθεωρημένου αλγόριθμου simplex και ενός πρωτεύονται – δυϊκού αλγόριθμου simplex εξωτερικών σημείων. Και οι δύο υλοποιήσεις έχουν γίνει στο MATLAB χρησιμοποιώντας το MATLAB's Parallel Computing Toolbox. Τα υπολογιστικά αποτελέσματα σε τυχαία αραιά και πυκνά γραμμικά προβλήματα παρουσιάζονται. Τα αποτελέσματα δείχνουν ότι οι προτεινόμενες υλοποιήσεις στη GPU είναι καλύτερες από τον αλγόριθμο εσωτερικών σημείων του MATLAB.