Heuristic algorithms (2025/26)

Schedule and classroom

The lessons take place

• on Wednesday, from 13.30 to 16.30, in classroom Alfa (Computer Science department)
• on Thursday, from 09.30 to 12.30, in classroom Alfa (Computer Science department)

Exam

The exam is written, usually composed of five parts:

1. combinatorial optimization problems: ground sets, objective function and feasibility
2. performance evaluation: quality and time, a priori and a posteriori
3. constructive heuristics and metaheuristics
4. exchange heuristics and metaheuristics
5. recombination heuristics and metaheuristics

The dates expected for the exams are (but please check on the official site):

• on 20/03/2026, from 14.30 to 17.00
• on 10/04/2026, from 14.30 to 17.00
• on 22/06/2026, from 10.30 to 13.00
• on 20/07/2026, from 10.30 to 13.00

Notice: The June and July calls overlap with those of Decision methods and models. Please, let me know in advance if you plan to take both exams (probably, one will be moved to the afternoon).

Lessons

Lecture notes in English are available. The students are welcome to report mistakes and obscurities.

Additional lecture notes for the Italian version of the course have been provided by another former student.

Lessons 1 (14th January 2026)

• Slides

Lesson 2 (14th January 2026)

• Slides

Lesson 3 (15th January 2026)

• Slides

Lesson 4 (21st January 2026)

• Slides

Lesson 5 (21st January 2026)

• Slides
• How not to do it (paper by I.P. Gent et al.)
• Testing heuristics: we have it all wrong (paper by J.N. Hooker)

Lesson 6 (22nd January 2026)

• Slides
• Wilcoxon's test explanation
• Wilcoxon's test example
• Wilcoxon's test Perl script
• Tiny Perl interpreter for Windows

Lesson 7 (28th January 2026)

• Slides

Lesson 8 (28th January 2026)

• Slides
• Approximation algorithms for the BPP and the KP (lecture notes by Marco Di Summa)
• Approximation algorithms for the SCP (lecture notes by Ravi Vazirani)

Lesson 9 (29th January 2026)

• Slides
• Constructive heuristics for the TSP
• Roll-out heuristics (paper by D. Bertsekas)

Lesson 10 (4th February 2026)

• Lecture notes
• Benchmark instances
• Code
• Scripts
• Best known results
• Wilcoxon's test Perl script
• Tiny Perl interpreter for Windows

Lesson 11 (4th February 2026)

• Slides
• Adaptive Reasoning Technique (paper by R. Patterson, E. Rolland, H. Pirkul)
• Greedy Randomized Adaptive Search Procedure (paper by M. Resende e C.C. Ribeiro)
• Ant System (paper by O. Cordón, F. Herrera, T. Stützle)
• Convergence of the Ant System (paper by W.J. Gutjahr)

Lessons 12 (5th February 2026)

• Lecture notes
• Code
• Scripts

Lesson 13 (11th February 2026)

Slides
• A general scheme of local search (paper by R.J.M. Vaessens, E.H.L. Aarts e J.K. Lenstra)

Lessons 14 (11th February 2026)

• Slides
• First-best and global-best strategies (paper by E.J. Anderson)

Lesson 15 (12th February 2026)

• Slides
• Survey (paper by R.K. Ahuja, O. Ergun, J.B. Orlin and A.P. Punnen)
• Lin-Kernighan (paper by S. Lin and B.W. Kernighan)
• Order-first route-second (paper by C. Prins, P. Lacomme and C. Prodhon)

Lesson 16 (18th February 2026)

• Lecture notes
• Code
• Scripts

Lesson 17 (18th February 2026)

• Slides
• Iterated Local Search (paper by H.R. Lourenco, O.C. Martin and T. Stützle)
• Variable Neighbourhood Search (paper by P. Hansen and N. Mladenovic)

Lesson 18 (19th February 2026)

• Slides

Lesson 19 (25th February 2026)

• Slides
• Simulated Annealing (book chapter by A.G. Nikolaev and S.H. Jacobson)
• Tabu Search (book chapter by M. Gendreau and J.-Y. Potvin)

Lesson 20 (25th February 2026)

• Lecture notes
• Code
• Scripts

Lesson 21 (26th February 2026)

• Slides
• Scatter Search and Path Relinking (paper by F. Glover, M. Laguna and R. Martì)

Lessons 22 (4th March 2026)

• Slides
• Genetic algorithms (book chapter by C.R. Reeves)

Lesson 23 (4th March 2026)

• Slides
• Constraint handling techniques (survey paper by C.A. Coello Coello)

Lesson 24 (5th March 2026)

• Lecture notes
• Code
• Scripts