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

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

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

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

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