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

Μοντέλα επιχειρησιακής έρευνας, πολυπλοκότητα αλγορίθμων, προβλήματα NP-hard. Γραμμικός προγραμματισμός: αλγόριθμος simplex, δυϊκή θεωρία, το πρόβλημα μεταφοράς. Ακέραιος προγραμματισμός: branch and bound - το πρόβλημα διαμέρισης, το πρόβλημα της ελάχιστης επικάλυψης συνόλου (minimum set covering), δυναμικός προγραμματισμός - το πρόβλημα του σακιδίου (knapsack problem), γενικευμένο knapsack, ευρετικοί αλγόριθμοι και τεχνικές αποτίμησης απόδοσης - λόγος προσεγγισιμότητας, το πρόβλημα  κομβικής επικάλυψης (vertex covering), μέγιστο ανεξάρτητο υποσύνολο, άνω και κάτω φράγματα, εμπειρική αποτίμηση ευρετικών μεθόδων. Mέθοδος τοπικής αναζήτησης: δομή γειτονιάς, τεχνικές αναζήτησης γειτονιάς, PLS-completeness, το πρόβλημα του πλανόδιου πωλητή (k-OPT), διαμέριση γράφων. Simulated annealing: ο αλγόριθμος του Metropolis, εφαρμογές, το πρόβλημα της μέγιστης τομής (max cut).