Heuristic Algorithms
A.Y. 2024/2025
Learning objectives
The course aims to
- present the main paradigms to design heuristic algorithms for complex decision problems with particular emphasis on combinatorial optimization problems
- discuss the a priori and a posteriori methods to evaluate the effectiveness and efficiency of heuristic algorithms
- perform experimental activities designing heuristic algorithms based on the study of the problem, implementing them on a computer in a programming language, evaluating and comparing their performance on benchmark data
- present the main paradigms to design heuristic algorithms for complex decision problems with particular emphasis on combinatorial optimization problems
- discuss the a priori and a posteriori methods to evaluate the effectiveness and efficiency of heuristic algorithms
- perform experimental activities designing heuristic algorithms based on the study of the problem, implementing them on a computer in a programming language, evaluating and comparing their performance on benchmark data
Expected learning outcomes
The student will learn the main techniques to design heuristic algorithms and to quantitatively assess their performance. The student will learn to design and implement in a programming language heuristic algorithms and to evaluate their performance.
Lesson period: First semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
First semester
Course syllabus
The teaching aims to:
- present general techniques for the design, implementation and evaluation of heuristic algorithms
- provide the students with a strong intuitive understanding of the general ideas underlying such algorithms
- provide the students with the practical ability to build effective and efficient algorithms
The teaching focuses on Combinatorial Optimization problems.
Introduction
* Classification of heuristic algorithms
* Some relevant Combinatorial Optimization problems
* Computational Complexity: definitions and parametrized complexity
* Theoretical performance analysis: approximate algorithms
* Experimental performance analysis
Constructive heuristics and metaheuristics
* Greedy algorithms
* Roll-out algorithms
* GRASP
* Ant Colony Optimization
Local search heuristics and metaheuristics
* Neighbourhood: definition and efficient exploration
* Very Large Neighborhood Search
* Iterated local search and Variable Neighborhood Search
* Simulated Annealing
* Tabu search
Recombination heuristics
* Scatter search and Path Relinking
* Genetic algorithms and evolutionary strategies
- present general techniques for the design, implementation and evaluation of heuristic algorithms
- provide the students with a strong intuitive understanding of the general ideas underlying such algorithms
- provide the students with the practical ability to build effective and efficient algorithms
The teaching focuses on Combinatorial Optimization problems.
Introduction
* Classification of heuristic algorithms
* Some relevant Combinatorial Optimization problems
* Computational Complexity: definitions and parametrized complexity
* Theoretical performance analysis: approximate algorithms
* Experimental performance analysis
Constructive heuristics and metaheuristics
* Greedy algorithms
* Roll-out algorithms
* GRASP
* Ant Colony Optimization
Local search heuristics and metaheuristics
* Neighbourhood: definition and efficient exploration
* Very Large Neighborhood Search
* Iterated local search and Variable Neighborhood Search
* Simulated Annealing
* Tabu search
Recombination heuristics
* Scatter search and Path Relinking
* Genetic algorithms and evolutionary strategies
Prerequisites for admission
Knowing the fundamental algorithms and data structures.
Knowing how to implement them in a programming language (preferably C).
Knowing the asymptotic complexity notation.
It is recommended to have passed the exam of Algorithms and Data Structures.
Knowing how to implement them in a programming language (preferably C).
Knowing the asymptotic complexity notation.
It is recommended to have passed the exam of Algorithms and Data Structures.
Teaching methods
The teaching consists of classroom-taught lectures.
Occasional practical activities in laboratory are possible.
Occasional practical activities in laboratory are possible.
Teaching Resources
Slides, lecture notes and survey papers on the web site
https://rcordoneha.ariel.ctu.unimi.it
https://rcordoneha.ariel.ctu.unimi.it
Assessment methods and Criteria
The exam is written, and its length ranges between two and three hours.
It requires to answer open questions on the topics of the teaching
and to solve problems applying the techniques presented in the teaching.
The evaluation of the exam is expressed on a scale of 30 points, keeping into account
the following aspects: knowledge of the topics, capacity of applying knowledge to the
solution of practical problems, capacity of critical reasoning, clarity and correct use of language.
It requires to answer open questions on the topics of the teaching
and to solve problems applying the techniques presented in the teaching.
The evaluation of the exam is expressed on a scale of 30 points, keeping into account
the following aspects: knowledge of the topics, capacity of applying knowledge to the
solution of practical problems, capacity of critical reasoning, clarity and correct use of language.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor:
Cordone Roberto
Shifts:
Turno
Professor:
Cordone RobertoEducational website(s)
Professor(s)