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

• Μορφοποίηση και εφαρμογές προβλημάτων ακέραιου και μεικτού ακέραιου προγραμματισμού.
• Ευφυείς χρήσεις δυαδικών μεταβλητών στη μορφοποίηση μοντέλων.
• Μέθοδος διακλάδωσης και φραγμού (branch and bound).
• Μέθοδος επίπεδων τομών (cutting planes).
• Σχεδιασμός και ανάλυση αλγορίθμων συνδυαστικής βελτιστοποίησης.
• Πολυπλοκότητα αλγορίθμων.
• Εφαρμογές σε δίκτυα και γραφήματα.
• Επίλυση προβλημάτων με τη χρήση τεχνικών τοπικής βελτιστοποίησης, δυναμικού προγραμματισμού, μυωπικών αλγορίθμων, προσεγγιστικών και ευρετικών μεθόδων.

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

• Γραπτή τελική εξέταση (70%)
• Ασκήσεις (30%)

1η Ενότητα

• Εισαγωγή – Επανάληψη γραμμικού προγραμματισμού – Σχέση ακέραιου και συνεχούς προγραμματισμού

2η Ενότητα

• Μορφοποίηση και εφαρμογές προβλημάτων ακέραιου προγραμματισμού – Ευφυείς χρήσεις δυαδικών μεταβλητών

3η Ενότητα

• Χαλαρώσεις και Όρια – Γραμμική χαλάρωση – Χαλάρωση Lagrange – Δυϊκότητα

4η Ενότητα

• Μέθοδοι επίλυσης προβλημάτων ακέραιου προγραμματισμού – Γραφική μέθοδος – Πλήρης και έμμεση απαρίθμηση – Δυναμικός προγραμματισμός – Μέθοδος διακλάδωσης και φραγμού (branch and bound) – Τεχνικές προεπεξεργασίας – Ισχύουσες ανισότητες – Σύσφιξη περιορισμών – Μέθοδος επίπεδων τομών (cutting planes)

5η Ενότητα

• Σχεδιασμός και ανάλυση αλγορίθμων – Πολυπλοκότητα αλγορίθμων – Κλάσεις πολυπλοκότητας

6η Ενότητα

• Προβλήματα συνδυαστικής βελτιστοποίησης – Matching, Matroids και ο μυωπικός αλγόριθμος – Γραφήματα, δέντρα, μονοπάτια, ροές

7η Ενότητα

• Τοπική αναζήτηση και βελτιστοποίηση – Προσεγγιστικές και ευρετικές μέθοδοι