Τεχνικές Σχεδίασης Προσεγγιστικών Αλγορίθμων Βασισμένες Στο Γραμμικό Προγραμματισμό

Abstract

Τα τελευταία χρόνια έχουν αναπτυχθεί πολλοί νέοι προσεγγιστικοί αλγόριθμοι για προβλήματα βελτιστοποίησης. Ένα μεγάλο ποσοστό αυτών βασίζεται στη θεωρία του γραμμικού προγραμματισμού. Οι αλγόριθμοι αυτοί χρησιμοποιούν δύο βασικές τεχνικές, την τεχνική της στρογγυλοποίησης (rounding) και το σχήμα πρωτεύον - δυϊκό (primal-dual). Η διπλωματική αυτή εργασία μελετάει και τις δύο τεχνικές με ιδιαίτερη έμφαση στην πρώτη και στις διάφορες υποκατηγορίες της. Χάριν πληρότητας, δίνεται αρχικά μία εισαγωγή στη μαθηματική θεωρία του γραμμικού προγραμματισμού.Οι προσεγγιστικοί αλγόριθμοι που βασίζονται στη μέθοδο στρογγυλοποίησης επιλύουν (βέλτιστα) ένα γραμμικό πρόγραμμα το οποίο αποτελεί χαλάρωση του προς επίλυση προβλήματος βελτιστοποίησης. Εν γένει, ωστόσο, η λύση που υπολογίζεται τοιουτοτρόπως έχει κλασματικές συνιστώσες. Οι περισσότεροι αλγόριθμοι λύνουν το εν λόγω γραμμικό πρόγραμμα μία φορά και κατασκευάζουν μία ακέραια (εφικτή) λύση μέσω κατάλληλης διαδικασίας στρογγυλοποίησης. Ωστόσο, αυτή η μέθοδος φαίνεται να μην εκμεταλλεύεται την πλήρη ισχύ του γραμμικού προγραμματισμού. Μία βελτιωμένη τεχνική είναι αυτή της επαναλαμβανόμενης στρογγυλοποίησης, στην οποία στρογγυλοποιούμε τη λύση σε φάσεις. Μετά από κάθε φάση, υπολογίζουμε εκ νέου την καλύτερη κλασματική λύση, διατηρώντας τη στρογγυλοποίηση που είχε πραγματοποιηθεί σε προηγούμενες φάσεις. Επιπλέον, η στρογγυλοποίηση μπορεί να γίνει τόσο με ντετερμινιστικό όσο και με randomized τρόπο. Ειδική έμφαση δίνεται στη randomized στρογγυλοποίηση.Οι προσεγγιστικοί αλγόριθμοι που βασίζονται στη μέθοδο πρωτεύοντος-δυϊκού λειτουργούν με ένα ζεύγος πρωτεύοντος και δυϊκού γραμμικού προγράμματος. Στην παρούσα εργασία εφαρμόζουμε αυτό το σχήμα μόνο για περιπτώσεις που όλοι οι συντελεστές του πρωτεύοντος και του δυϊκού γραμμικού προγράμματος είναι μη αρνητικοί. Πρόσφατα, αποδείχθηκε ότι η εν λόγω μέθοδος μπορεί να εφαρμοστεί και σε περιπτώσεις που εμφανίζονται και αρνητικοί συντελεστές. Σημειώνεται ότι οι αλγόριθμοι αυτής της κατηγορίας είναι γενικά πιο γρήγοροι από αυτούς της πρώτης κατηγορίας.