Heuristic algorithms (2023/24)

Schedule and classroom

The lessons take place

• on Thursday, from 14.30 to 16.30, in classroom 201
• on Friday, from 14.30 to 16.30, in classroom 100

Notice: On the 15th December, the lesson will start at 14.30 and end at 16.00, to allow the teacher to take part to a master's thesis session.

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.

The students can access the 2018/19 edition web page of the course in Italian, but the material has not been updated.

Lecture notes in English have been published last year. The students are welcome to report mistakes: apart from correcting the mistakes pointed out, I am not planning further updates in the near future.

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

Lesson 1 (29th September 2022)

• Slides

Lesson 2 (5th October 2022)

• Slides

Lesson 3 (6th October 2022)

• Slides

Lesson 4 (12th October 2022)

• Slides

Lesson 5 (13th October 2022)

• 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 (19th October 2022)

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

Lesson 7 (20th October 2022)

• Slides

Lesson 8 (26th October 2022)

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

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

Lesson 10 (2nd December 2022)

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

Lesson 11 (3rd December 2022)

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

• Lecture notes
• Code
• Scripts

Lesson 13 (10th November 2022)

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

Lessons 14 (16th November 2022)

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

Lesson 15 (17th November 2022)

• 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 (23rd November 2022)

• Lecture notes
• Code
• Scripts

Lesson 17 (24th November 2022)

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

• Slides

Lesson 19 (1st December 2022)

• 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 (14th December 2022)

• Lecture notes
• Code
• Scripts

Lesson 21 (15th December 2022)

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

Lessons 22 (21st December 2022)

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

Lesson 23 (11th January 2023)

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

Lesson 24 (12th January 2023)

• Lecture notes
• Code
• Scripts