Αλγοριθμική Επιχειρησιακή Έρευνα

Το μάθημα καλύπτει βασικά μαθηματικά μοντέλα λήψης αποφάσεων και παρουσιάζει αλγοριθμικές τεχνικές επίλυσής τους. Εστιάζει στο γραμμικό προγραμματισμό και στον αλγόριθμο simplex, στην δυϊκή θεωρία και στα προβλήματα μεταφοράς. Στον ακέραιο προγραμματισμό περιγράφει τις τεχνικές branch and bound για προβλήματα packing, covering και σακιδίου (knapsack problem) και του γενικευμένου γραμμικού προγραμματισμού για προβλήματα τεμαχισμού (cutting stock problems). Περιγράφει τεχνικές αποτίμησης της απόδοσης των αλγορίθμων (εμπειρική αποτίμηση, λόγος προσεγγισιμότητας). Αναπτύσσει αλγόριθμους τοπικής αναζήτησης και μελετά την δομή γειτονιάς και τις μεθόδους αναζήτησης στις γειτονιές για τα προβλήματα του πλανόδιου πωλητή (γειτονιές κ-OPT), της μέγιστης τομής (max cut) και της διαμέρισης γράφων (bipartitioning).