Heuristic Μethods
Objectives:
This course aims to an introduction to modern metaheuristic methods in real-world large-scale problem solving, where a compromise between the solution quality and the computational time is required.
Skills:
By successfully attending this course, graduate students will develop skills related to i) modeling of complex practical problems and ii) the algorithmic solution in a short computational time.
Prerequisites:
Good knowledge of operational research, programming, and data structures.
Content:
In solving optimization problems various exact mathematical programming algorithms are usually applied. However, such conventional methods are not usually efficient with combinatorial or global optimization problems, especially when the problem has a large and complex search space. The majority of these computational problems belong to the NP-hard class and thus, a solution in polynomial time is not possible (unless P = NP).
In order to efficiently solve such problems several heuristic methods have also been studied in an attempt to find a compromise sub-optimal solution in a short computation time. Heuristic search methods are usually produced using simple intuitive and creative thinking, and are often useful in local search to quickly find good solutions in a small search area. Metaheuristic methods are higher level methods, which systematically coordinate the whole search process by the heuristic methods. Although, metaheuristic algorithms cannot guarantee finding a global optimal solution, they often provide very good results in several practical problems.
The following topics will be studied in this module:
Introduction to computationally hard combinatorial and global optimization problems and also to exhaustive search methods. Basic concepts such as solution representation, local search, neighborhoods, and local optimal. Introduction to variable neighborhood search, genetic algorithms, nature inspired algorithms, (e.g., swarm intelligence), tabu search, simulated annealing. Applications of metaheuristic algorithms in routing and inventory problems. Statistical analysis of computational experiments of heuristics.
Textbooks:
Μαρινάκης Ι., Μαρινάκη Μ., Ματσατσίνης Ν. Φ., Ζοπουνίδης Κ., (2011). Μεθευρετικοί και Εξελικτικοί Αλγόριθμοι σε Προβλήματα Διοικητικής Επιστήμης, Εκδόσεις Κλειδάριθμος
Zbigniew Michalewicz, David B. Fogel, (2004). How to Solve It: Modern Heuristics, 2nd ed., Springer.
Assessment:
The written exam is worth 50% of the final mark and the coursework for the course is worth the remaining 50% of the final mark. Each student is required to submit two programming deliverables. These two assignments are due on the tenth teaching week and on the date of the course written examination, respectively.
