Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων

Abstract

Linear Programming deals with the optimization (minimization or maximization) of an objective function under certain linear (equality or inequality) constraints. Great progress has been made in mathematical programming since the introduction of the simplex algorithm in 1947 by Dantzig. Researchers' interest turned to polynomial complexity algorithms in order to solve large-scale linear problems since the moment that the worst-case complexity of the simplex algorithm proved to be exponential. In the early 1990s, a new class of simplex type algorithms appeared in the international bibliography. The algorithms of this class are called exterior point or two-path algorithms. The first paper, in which an exterior point algorithm was presented, published in 1991 by Paparrizos. The primal exterior point algorithm has two main computational drawbacks: 1.It is difficult to construct "good moving directions". The two paths depend on the initial feasible direction and the initial feasible vertex. 2.There is no known way of moving into the interior of the feasible region. This movement achieves the search for computationally good directions.Forcing the exterior path of an exterior point algorithm to become a dual feasible simplex path results in an algorithm free of the above-mentioned computational drawbacks.In this thesis, a computational improvement of the primal dual two-path simplex algorithm proposed by Paparrizos is presented. More specifically, the new algorithm that was implemented moves in the interior of the feasible region and not in its' frontier. Moving to the interior of the feasible region results in an algorithm free of the stalling and cycling phenomena. Extensive computations studies were conducted in order to study the practical effectiveness of the algorithm. More specifically, three different computational studies were conducted. Presolve techniques, scaling techniques, tolerances and explicit inverse of the basis when needed were applied in order to solve large-scale linear problems. In the computational studies, the problems that were used are randomly generated sparse linear problems with a dual feasible initial basic solution, randomly generated sparse linear problems with an initial basic solution that is neither primal nor dual feasible and benchmark linear problems (www.netlib.org). The computational results for the new algorithm are encouraging. More specifically, in randomly generated sparse linear problems of size 1200x1200 with an initial basic solution that is neither primal nor dual feasible and density 2.5%, 5% and 10%, the new algorithm is 169, 126 and 128 times faster than the original simplex algorithm and 1.16, 1.10 and 1.15 times faster than the primal dual two-path simplex algorithm, respectively. This improvement is translated to CPU time as follows. The new algorithm is 108, 97 and 98 times faster than the original simplex algorithm and 1.14, 1.08 and 1.17 times faster than the primal dual two-path simplex algorithm, respectively.

Ο Γραμμικός Προγραμματισμός ασχολείται με τη βελτιστοποίηση (ελαχιστοποίηση ή μεγιστοποίηση) μιας γραμμικής συνάρτησης κάτω από ορισμένους γραμμικούς (ισοτικούς ή ανισοτικούς) περιορισμούς. Από την ανακάλυψη του αλγορίθμου 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 αντίστοιχα.