Heuristic Methods

Recommended Prerequisites

Optimization, algorithms, programming, probability and statistics, English language.

Teaching Methods

Teaching is organized as two complementary components, theoretical and practical. Lectures (T) are mainly of an expository nature, but are also used to answer questions of general interest to the class. Practical (PL) sessions aim to consolidate the concepts presented in the lectures through exercises and the study of simplified cases. A practical project involving the modelling and heuristic solving of problems in the field of operations research is also proposed and assessed. 

Learning Outcomes

The aim is to provide students with the ability to systematically design heuristic approaches to solve concrete practical problems, to apply such approaches, and to evaluate the results obtained, with an emphasis on combinatorial and/or numerical optimization problems. Some of the most relevant heuristic methods at present and their most successful applications are also presented, with particular focus on the heuristic principles they implement, aspects of their performance, and questions related to their practical use.

Work Placement(s)

No

Syllabus

1. Introduction

1.1. Problem solving

1.2. Constructive heuristics and improvement heuristics

1.3. Relation to exact methods

2. Optimization problem modelling

2.1. Definition of the decision space

2.2. Solution representation

2.3. Evaluation of solution quality

2.4. Construction rules and neighbourhood structures

2.5. Constraint handling

3. Heuristics and meta-heuristics

3.1. Greedy construction, GRASP, beam search, ant colony optimisation

3.2. Hill climbing, simulated annealing, tabu search, iterated local search

3.3. Evolutionary algorithms and particle swarm optimisation

3.4. Estimation of distribution algorithms

4. Performance issues

4.1. Problem difficulty

4.2. Notions of performance

4.3. Parameter tuning and parameter adaptation

4.4. Benchmarking.

Assessment Methods

Assessment
Project: 35.0%
Exam: 65.0%

Bibliography

Rafael Martí, Panos M. Pardalos, Mauricio G. C. Resende, Handbook of Heuristics, Springer, 2018.

Éric D. Taillard, Design of Heuristic Algorithms for Hard Optimization, Springer, 2023. Open access.

Mauricio G. C. Resende and Celso C. Ribeiro, Optimization by GRASP, Springer, 2016.

Marco Dorigo and Thomas Stützle, Ant Colony Optimization, MIT Press, 2004.

Holger H. Hoos and Thomas Stützle, Stochastic Local Search, Morgan Kaufmann, 2004.

D.-Z. Du, K.-I Ko, and X. Hu, Design and Analysis of Approximation Algorithms, Springer, 2012.

A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing, 2^nd ed., Springer, 2015.

S. S. Skiena, The Algorithm Design Manual, 3^rd ed., Springer, 2020.

A. Laaksonen, Guide to Competitive Programming, 3^rd ed., Springer, 2024.