Συνδυαστική Βελτιστοποίηση

Περιεχόμενο μαθήματος

Tο μάθημα εξετάζει τη θεωρία, τους αλγορίθμους και τις εφαρμογές της διακριτής (επίσης γνωστής και ως 'συνδυαστική') βελτιστοποίησης, με έμφαση σε προβλήματα που αφορούν ροές, μονοπάτια και ταιριάσματα σε γραφήματα.

Συγκεκριμένα, το μάθημα παρουσιάζει αλγορίθμους για τα προβλήματα του συντομότερου μονοπατιού, της μέγιστης ροής, της ροής ελαχίστου κόστους, του ταιριάσματος μέγιστου μεγέθους ή μέγιστου βάρους (κυρίως σε διμερή γραφήματα) και, τέλος, του ευσταθούς ταιριάσματος σε διμερή γραφήματα.

Πέραν της επίλυσης τέτοιων προβλημάτων με χρήση ειδικών αλγορίθμων, οι φοιτητές αναμένεται να μορφοποιούν εφαρμογές και πραγματικά προβλήματα ως προβλήματα μονοπατιών, ροών και ταιριασμάτων σε γραφήματα. Επιπλέον, το μάθημα παρουσιάζει γενικές μεθόδους για προβλήματα διακριτής βελτιστοποίησης τα οποία μοντελοποιούνται ως προβλήματα Ακέραιου Προγραμματισμού, δηλαδή μεθόδους Κλάδου-και-Φράγματος και μεθόδους Κλάδου-και-Τομής.

Το περιεχόμενο του μαθήματος περιλαμβάνει τις παρακάτω ενότητες:

• Ροές σε δίκτυα και ακέραιος προγραμματισμός
• Αλγόριθμοι συντομότερων μονοπατιών: Dijkstra, Bellman-Ford, Floyd-Warshall
• Αλγόριθμοι μέγιστης ροής και ροής ελαχίστου κόστους
• Αλγόριθμοι ταιριασμάτων σε διμερή γραφήματα: ταίριασμα μέγιστου μεγέθους, ταίριασμα μέγιστου βάρους, ευσταθή ταιριάσματα
• Μοντελοποίηση εφαρμογών ως προβλήματα ροής: χρονοπρογραμματισμός έργων, ανάθεση εργασιών σε μηχανές, εκπροσώπηση, κατανομή επενδύσεων κλπ.
• Ακέραιος προγραμματισμός: αλγόριθμοι κλάδου και φράγματος, ο προσθετικός αλγόριθμος του Balas, αλγόριθμοι κλάδου και τομής
• Εφαρμογές ακέραιου προγραμματισμού
• Δέντρα: ιδιότητες, αλγόριθμοι διάσχισης, αλγόριθμοι εύρεσης ελάχιστου συνεκτικού δέντρου, δέντρα Steiner.

Μαθησιακά αποτελέσματα

Μετά την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα είναι σε θέση:

• Να περιγράφουν και να χειρίζονται τις θεμελιώδεις έννοιες, τα βασικά θεωρήματα και τις μεθόδους ή αλγορίθμους Συνδυαστικής Βελτιστοποίησης.
• Να εκτελούν τους υπολογισμούς για συγκεκριμένες μεθόδους ή αλγορίθμους Συνδυαστικής Βελτιστοποίησης σε λελογισμένου μεγέθους προβλήματα, π.χ., βήματα αλγορίθμου μέγιστης ροής, βήματα ακέραιου προγραμματισμού.
• Να μοντελοποιούν πραγματικά προβλήματα από ένα εύρος εφαρμογών ως προβλήματα Συνδυαστικής Βελτιστοποίησης και να προσδιορίζουν τη κατάλληλη μέθοδο ή αλγόριθμο βελτιστοποίησής τους.
• Να αντιλαμβάνονται τις αποδείξεις των σχετικών θεωρημάτων και της γενικότερης μαθηματικής θεμελίωσης του Συνδυαστικής Βελτιστοποίησης, να μπορούν να επικαλούνται συγκεκριμένα θεωρήματα (π.χ. μέγιστης ροής-ελάχιστης τομής) προκειμένου να επιλύσουν αποτελεσματικότερα σχετικά προβλήματα και να μπορούν να διατυπώσουν τις απλούστερες από αυτές τις αποδείξεις.
• Να μελετούν αυτόνομα και να εμβαθύνουν στην τρέχουσα βιβλιογραφία από επιστημονικά περιοδικά και βιβλία Συνδυαστικής Βελτιστοποίησης, ακόμη και σε γνωστικές περιοχές οι οποίες οριακά εντάσσονται στο περιεχόμενο του μαθήματος.