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

Θα δοθεί έμφαση στην αλγοριθμική επίλυση προβλημάτων βελτιστοποίησης δικτύων αλλά και στη μοντελοποίηση με χρήση ακεραίου προγραμματισμού.

Στόχοι Μαθήματος

Το μάθημα αυτό στοχεύει σε μια εισαγωγή στα μοντέλα βελτιστοποίησης δικτύων και στον ακέραιο προγραμματισμό.

Προαπαιτούμενες Γνώσεις

Γνώσεις επιχειρησιακής έρευνας.

Περιεχόμενα

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