Heuristic Methods

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.

Objectives

not available

Prerequisites

not available

Syllabus

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.