Heuristic Methods

Recommended Prerequisites

Optimization, programming, probability and statistics, English language.

Teaching Methods

Teaching is organized in 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 modeling and heuristic solving of problems in the field of operations research is also proposed and assessed.

Learning Outcomes

It is intended to provide students with the ability to systematically delineate heuristic approaches leading to practical solving of concrete problems, to apply such approaches, and to evaluate the results obtained, with an emphasis on combinatorial and/or numerical optimization problems. It is also intended to present some of the most relevant heuristic methods at present, and their most successful applications, focusing in particular on the heuristic principles they implement, on aspects of their performance, and on questions related to their practical deployment. Finally, it is intended to highlight the symbiotic relationship between heuristic methods and machine learning.

Work Placement(s)

No

Syllabus

1. Introduction
1.1. Problem solving
1.2. Construtive heuristics and improvement heuristics
1.3. Heuristic principles: analogy, induction, decomposition, intensification, diversification, recombination, greedy improvement, randomisation, temporary degradation, restart
1.4. Relation to exact methods
2. Optimization problem formulation
2.1. Definition of the search space
2.2. Solution representation
2.3. Evaluation of solution quality
2.4. Neighbourhood structures
2.5. Constraint handling
3. Heuristics and meta-heuristics
3.1. Simulated annealing, tabu search, iterated local search
3.2. Evolutionary algorithms and particle swarm optimisation
3.3. Ant colony optimization
3.4. GRASP
3.5. Estimation of distribution algorithms
4. Performance issues
4.1. Problem difficulty
4.2. Notions of performance
4.3. Parameter tuning
4.4. Parameter adaptation, self-adaptation and learning
4.5. Hyper-heuristics
4.6. Deconstruction of heuristics

Head Lecturer(s)

Carlos Manuel Mira da Fonseca

Assessment Methods

Assessment
Project: 35.0%
Exam: 65.0%

Bibliography

George Polya, How to Solve It: A New Aspect of Mathematical Method. Princeton University Press, 1945. Reprinted by Penguin Books, 1990.
Fred Glover and Manuel Laguna,Tabu Search, Kluwer, 1997.
Thomas Bäck, David B Fogel, and Zbigniew Michalewicz (eds.), Evolutionary Computation 1 - Basic Algorithms and Operators, CRC Press, 2000.
Thomas Bäck, David B Fogel, and Zbigniew Michalewicz (eds.), Evolutionary Computation 2 - Advanced Algorithms and Operators, CRC Press, 2000.
Marco Dorigo and Thomas Stützle, Ant Colony Optimization, MIT Press, 2004.
Holger H. Hoos and Thomas Stützle, Stochastic Local Search, Morgan Kaufmann, 2014.
Mauricio G. C. Resende and Celso C. Ribeiro, Optimization by GRASP, Springer, 2016.
Rafael Martí, Panos M. Pardalos, Mauricio G. C. Resende, Handbook of Heuristics, Springer, 2018.