1η Ενότητα
(4 Ώρες)
|
Εισαγωγή – Επανάληψη γραμμικού προγραμματισμού – Σχέση ακέραιου και συνεχούς προγραμματισμού |
2η Ενότητα
(4 Ώρες)
|
Μορφοποίηση και εφαρμογές προβλημάτων ακέραιου προγραμματισμού – Ευφυείς χρήσεις δυαδικών μεταβλητών |
3η Ενότητα
(4 Ώρες)
|
Χαλαρώσεις και Όρια – Γραμμική χαλάρωση – Χαλάρωση Lagrange – Δυϊκότητα |
4η Ενότητα
(20 Ώρες)
|
Μέθοδοι επίλυσης προβλημάτων ακέραιου προγραμματισμού – Γραφική μέθοδος – Πλήρης και έμμεση απαρίθμηση – Δυναμικός προγραμματισμός - Μέθοδος διακλάδωσης και φραγμού (branch and bound) – Τεχνικές προεπεξεργασίας - Ισχύουσες ανισότητες – Σύσφιξη περιορισμών – Μέθοδος επίπεδων τομών (cutting planes) |
5η Ενότητα
(6 Ώρες)
|
Σχεδιασμός και ανάλυση αλγορίθμων – Πολυπλοκότητα αλγορίθμων – Κλάσεις πολυπλοκότητας |
6η Ενότητα
(6 Ώρες)
|
Προβλήματα συνδυαστικής βελτιστοποίησης – Matching, Matroids και ο μυωπικός αλγόριθμος - Γραφήματα, δέντρα, μονοπάτια, ροές |
7η Ενότητα
(6 Ώρες)
|
Τοπική αναζήτηση και βελτιστοποίηση – Προσεγγιστικές και ευρετικές μέθοδοι |