Προσεγγιστικοί Αλγόριθμοι Για Συνδυαστικά Προβλήματα Στοχαστικής Βελτιστοποίησης

Abstract

Ο σκοπός της διπλωματικής αυτής εργασίας είναι η μελέτη αλγορίθμων για μια ενδιαφέρουσα παραλλαγή προβλημάτων συνδυαστικής βελτιστοποίησης στην οποία δε γνωρίζουμε με ακρίβεια τα δεδομένα εισόδου, αλλά γνωρίζουμε μόνο μία πιθανοτική κατανομή πάνω σε αυτά. Τέτοια προβλήματα εμπίπτουν στο ευρύτερο πεδίο της Στοχαστικής Βελτιστοποίησης. Σκοπός της Στοχαστικής Βελτιστοποίησης είναι η μοντελοποίηση της αβεβαιότητας στα δεδομένα εισόδου ενός προβλήματος. Η λήψη αποφάσεων σε συνθήκες αβεβαιότητας για τις μελλοντικές απαιτήσεις προκύπτει συχνά σε πολλές περιοχές, όπως σε προβλήματα σχεδιασμού δικτύων οποιασδήποτε φύσης, στα οποία δεν είναι ρεαλιστικό να θεωρήσουμε ότι γνωρίζουμε εξαρχής το ακριβές σύνολο των απαιτήσεων μας. Σε τέτοιες περιπτώσεις λοιπόν, οι απαιτήσεις δε μας είναι γνωστές με ακρίβεια, αλλά μέσω μοντέλων προσομοίωσης, ερευνών και μοντέλων προβλέψεων, μπορούμε να αποκτήσουμε στατιστικά δεδομένα για αυτές. Επίσης, αν και μπορούμε να πάρουμε πιο αποτελεσματικές αποφάσεις όταν λάβουμε τις ακριβείς πληροφορίες, το κόστος των αποφάσεων αυτών θα είναι τότε πιο ακριβό. Αυτό αντανακλάτην απόλυτα λογική αύξηση του κόστους για αποφάσεις που πρέπει να παρθούν και να υλοποιηθούν πολύ άμεσα, σε αντίθεση με τις αποφάσεις που μπορούμε να λάβουμε εκ των προτέρων και οι οποίες υλοποιούνται σε μεγαλύτερο βάθος χρόνου.Η πληροφορία σε τέτοια προβλήματα μας δίνεται σταδιακά, σε διακριτές στιγμές στο χρόνο που τις ονομάζουμε στάδια (stages). Θα ασχοληθούμε αρχικά με προβλήματα 2 σταδίων (2-stage), τα οποία αποτελούν την αφετηρία για οποιονδήποτε θέλει να ασχοληθεί με το πεδίο αυτό, και στη συνέχεια με προβλήματα πολλών σταδίων (multistage), και θα ορίσουμε τα προβλήματα βελτιστοποίησης μας σε σχέση με τη μέση τιμή του κόστους που προκύπτει σε όλα τα στάδια. Πιο συγκεκριμένα, ο στόχος μας είναι να κάνουμε την καλύτερη δυνατή επιλογή στο πρώτο στάδιο ώστε η μέση τιμή του κόστους που θα προκύψει σε όλα τα στάδια να είναι η ελάχιστη δυνατή. Ενα πολύ σημαντικό σημείο σε τέτοια προβλήματα είναι το πως μας δίνονται οι πιθανοτικές πληροφορίες. Θα επικεντρωθούμε στο λεγόμενο black-box μοντέλο, το οποίο μας δίνει τη δυνατότητα να μοντελοποιήσουμε αυθαίρετες κατανομές με κάθε είδους συσχετισμούς.Την τελευταία δεκαετία έχει γίνει αρκετή δουλειά στην περιοχή αυτή και θα παρουσιάσουμε ένα μέρος αυτής. Η δειγματοληψία (sampling) θα παίξει κεντρικό ρόλο καθώς είναι συνυφασμένη με το black-box μοντέλο. Θα χρησιμοποιήσουμε πολλές και διαφορετικές τεχνικές από πεδία όπως η θεωρία πιθανότητας και η γραμμική και κυρτή βελτιστοποίηση ώστε να προσεγγίσουμε τα προβλή-ματα αυτά. Προσπαθήσαμε να κρατήσουμε τις μεθόδους που παρουσιάζουμε όσο πιο γενικές γίνεται, με σύντομες αναφορές στις εφαρμογές τους, κυρίως σε προβλήματα κάλυψης (Set Cover, Vertex Cover) και προβλήματα χωροθέτησης υπηρεσιών (Facility Location Problems). Ελπίζουμε ότι το υλικό που θα παρουσιάσουμε θα επιτρέψει στον αναγνώστη να αποκτήσει μια καλή εικόνα για τα συνδυαστικά προβλήματα στοχαστικής βελτιστοποίησης και να κατανοήσει τις εγγενείς δυσκολίεςπου παρουσιάζουν και που πηγάζουν από το πιθανοτικό κομμάτι της εισόδου.