Heuristic algorithms

A.Y. 2020/2021
6
Max ECTS
48
Overall hours
SSD
INF/01
Language
English
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
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.
Course syllabus and organization

Single session

Responsible
Lesson period
First semester
Asynchronous lessons will be videotaped, showing the teacher's desktop with an audio comment.
They will be organised so as to cover the topics of the syllabus.
Synchronous lessons following the official schedule will provide
time for reviewing and deepening the concepts introduced in the videotaped lessons.
They will take place exploiting the platform MS-Teams.
Instructions on how to take part to the synchronous lessons will be published in advance
on the Ariel pages of the teaching. The same will hold for the
material and the notices concerning updates on the modifications of rules imposed by Covid-19.
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
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.
Teaching methods
The teaching consists of classroom-taught lectures.
Occasional practical activities in laboratory are possible.
Teaching Resources
Slides, lecture notes and survey papers on the course web page
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.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor: Cordone Roberto
Educational website(s)
Professor(s)
Reception:
By appointment
DI - Via Celoria 10, Milan