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

Εξάμηνο μαθήματος
2ου εξαμήνου
Κατηγορία μαθήματος
Επιλογής
Πιστωτικές Μονάδες
7,5
Διδάσκοντες

Ο. Τελέλης

Στοχος

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

  • Αναπτύσσουν την τυπική/αφηρημένη μαθηματική αναπαράσταση ενός προβλήματος συνδυαστικής βελτιστοποίησης, δεδομένης της περιγραφής του σε φυσική γλώσσα και των διαθέσιμων δεδομένων εισόδου.
  • Επιλέγουν τις κατάλληλες μεθόδους καθολικής ή προσεγγιστικής επίλυσης, για δεδομένη μαθηματική αναπαράσταση ενός προβλήματος.
  • Διακρίνουν υπολογιστικά εύκολα και δύσκολα προβλήματα.

Αποτιμούν τόσο τη λύση ενός μαθηματικού μοντέλου βελτιστοποίησης, όσο και την επίδοση της μεθόδου επίλυσης.

Περιεχομενα

  • Βελτιστοποίηση Συνεχών Συναρτήσεων.
  • Γραμμικός Προγραμματισμός. Μοντελοποίηση, Εφικτές και Βέλτιστες Λύσεις, Αλγόριθμος Simplex.
  • Δυϊκότητα Γραμμικού Προγραμματισμού. Σχέση Αρχικού – Δυϊκού Γραμμικού Προγράμματος, Βασικές Προτάσεις, Οικονομική Ερμηνεία, Δυϊκή Simplex, Ανάλυση Ευαισθησίας.
  • Ακέραιος Προγραμματισμός. Μοντελοποίηση, Παραδείγματα, Εφικτότητα, Γραμμική Χαλάρωση Αλγόριθμος Διακλάδωσης και Φραγής.
  • Βέλτιστες Ροές και Τομές σε Γραφήματα. Μέγιστη Ροή, Ελάχιστη Τομή, Ροές Ελάχιστου Κόστους, Πρόβλημα Μεταφοράς.
  • Βέλτιστα Ταιριάσματα. Μέγιστο Ταίριασμα, Τέλειο Ταίριασμα Ελάχιστου Κόστους.
  • Υπολογιστική Δυσκολία και Προσεγγιστικοί Αλγόριθμοι. Κλάσεις P και NP, Δυσκολία Προβλημάτων Βελτιστοποίησης, Παραδείγματα Προσεγγιστικών Αλγορίθμων.
  • Συνδυαστικοί Προσεγγιστικοί Αλγόριθμοι. Κάλυψη/Συσκευασία Συνόλου, Πρόβλημα Σακιδίου, Δέντρο Steiner, Πρόβλημα Πλανόδιου Πωλητή, Ανάθεση σε Παράλληλες Μηχανές.
  • Προσέγγιση μέσω Γραμμικού Προγραμματισμού. Τυχαιοκρατική Στρογγυλοποίηση, Προσέγγιση μέσω  Δυϊκού Γραμμικής Χαλάρωσης, Εφαρμογές.
  • Ευριστικές Μέθοδοι. Τοπική Αναζήτηση και Γειτονιές Λύσεων, Αναρρίχηση Λόφου, Προσομοιωμένη Ανόπτηση, Πρόβλημα Μέγιστης Τομής, Πρόβλημα Πλανόδιου Πωλητή.

Ενδεικτικη βιβλιογραφια

  • W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver. Combinatorial Optimization. Wiley Interscience, 1997.
  • D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
  • V. V. Vazirani. Approximation Algorithms. Springer, 2010.
  • W. Michiels, E. Aarts, J. Korst. Theoretical Aspects of Local Search. Springer, 2007.
  • C. H. Papadimitriou, K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998.
  • J. Kleinberg, E. Tardos. Algorithm Design, Pearson, 2005.