Παρουσίαση/Προβολή

Ώρες γραφείου

Προτεινόμενο σύγγραμμα

Παπαρρίζος Κ., Σαμαράς Ν., Σιφαλέρας Α., Δικτυακή Βελτιστοποίηση, Εκδόσεις Ζυγός, 2009.

Περιεχόμενο μαθήματος

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

Μαθησιακοί στόχοι

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

Μέθοδοι αξιολόγησης

Η αξιολόγηση για το τρέχον ακαδημαϊκό έτος, θα γίνει με γραπτή τελική εξέταση (100%).

Ενδεικτική Ξενόγλωσση βιβλιογραφία

• Schrijver A., Combinatorial Optimization: Polyhedra and Efficiency, Springer, Berlin, 2003.
• Korte B. and Vygen J., Combinatorial Optimization: Theory and Algorithms, 4th Εdition, Springer-Verlag Berlin Heidelberg, Series: Algorithms and Combinatorics (Vol. 21), 2007.
• Cook W.J., Cunningham W.H., Pulleyblank W.R. and Schrijver A., Combinatorial Optimization, John Wiley and Sons, New York, 1998.
• Papadimitriou C.H. and Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.
• Lee J., A First Course in Combinatorial Optimization, Series: Cambridge Texts in Applied Mathematics (No. 36), 2004.
• Ahuja, R.K., Magnanti T.L. and Orlin J.B., Network Flows: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.