Heuristic algorithms (2024/25)

Schedule and classroom

The lessons take place

• on Thursday, from 14.30 to 16.30, in classroom 503 (Centro Universitario)
• on Friday, from 14.30 to 16.30, in classroom 503 (Centro Universitario)

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

Lessons

The videorecordings of the lessons are available at the Ariel web site of the course.

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.

Lesson 1 (26th September 2024)

• Slides

Lesson 2 (27th September 2024)

• Slides

Lesson 3 (3rd October 2024)

• Slides

Lesson 4 (4th October 2024)

• Slides

Lesson 5 (10th October 2024)

• 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 (11th October 2024)

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

Lesson 7 (17th October 2024)

• Slides

Lesson 8 (18th October 2024)

• 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 (24th October 2024)

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

Lesson 10 (25th October 2024)

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

Lesson 11 (31st October 2024)

• 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 (7th November 2024)

• Lecture notes
• Code
• Scripts

Lesson 13 (8th November 2024)

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

Lessons 14 (14th November 2024)

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

Lesson 15 (15th November 2024)

• 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 (21st November 2024)

• Lecture notes
• Code
• Scripts

Lesson 17 (22nd November 2024)

• 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 (28th November 2024)

• Slides

Lesson 19 (29th November 2024)

• 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 (5th December 2024)

• Lecture notes
• Code
• Scripts

Lesson 21 (6th December 2024)

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

Lessons 22 (12th December 2024)

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

Lesson 23 (13th December 2024)

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

Lesson 24 (19th December 2024)

• Lecture notes
• Code
• Scripts