Heuristic algorithms (2022/23)

Schedule and classroom

The lessons take place

  • on Thursday, from 14.30 to 16.30, in classroom 303
  • on Friday, from 14.30 to 16.30, in classroom 303

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
that include theoretical questions and numerical exercises.

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

  • on 24/01/2023, from 14.30 to 17.00 in classroom V9 (via Venezian)
  • on 07/02/2023, from 14.30 to 17.00 in classroom 109 (via Celoria)
  • on 21/02/2023, from 14.30 to 17.00 in classroom V8 (via Venezian)
  • on 16/06/2023, from 14.30 to 17.00 in classroom V7 (via Venezian)
  • on 21/07/2023, from 14.30 to 17.00 in classroom V7 (via Venezian)
  • on 15/09/2023, from 14.30 to 17.00 in classroom V7 (via Venezian)

Notice: The July and September call overlap with those of Decision methods and models. Please, let me know in advance if you plan to take both exams.

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 provided by a former student. I have made a quick revision, and added solved exercises and notes on the laboratory sessions. 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)

Introduction: basics and classification of heuristic algorithms

Lesson 2 (30th September 2022)

Combinatorial Optimization: problems on sets, logical functions, matrices and graphs

Lesson 3 (6th October 2022)

A priori evaluation of algorithm efficiency: parameterized complexity and average-case complexity

Lesson 4 (7th October 2022)

A priori evaluation of algorithm effectiveness: deterministic and randomized approximation

Lesson 5 (13th October 2022)

A posteriori evaluation of heuristic algorithms (1)

Lesson 6 (14th October 2022)

A posteriori evaluation of heuristic algorithms (2)

Lesson 7 (20th October 2022)

Constructive heuristics: basic definitions and exact algorithms

Lesson 8 (21st October 2022)

Constructive heuristics: nonexact algorithms

Lesson 9 (27th November 2022)

Constructive heuristics: extensions of the basic scheme

Lesson 10 (28th November 2022)

Laboratory on constructive and destructive heuristics

Lesson 11 (3rd November 2022)

Constructive metaheuristics: Tabu Greedy, GRASP and Ant System

Lessons 12 (4th November 2022)

Laboratory on constructive metaheuristics

Lesson 13 (10th November 2022)

Exchange heuristics: neighbourhood definition

Lessons 14 (11th November 2022)

Exchange heuristics: exploration complexity

Lesson 15 (17th November 2022)

Very Large Neighbourhood Search

Lesson 16 (18th November 2022)

Laboratory on exchange heuristics

Lesson 17 (24th November 2022)

Exchange metaheuristics: Multi-start, Iterated Local Search and Variable Neighbourhood Search

Lesson 18 (25th November 2022)

Exchange metaheuristics: Variable Neighbourhood Descent and Dynamic Local Search

Lesson 19 (1st December 2022)

Exchange metaheuristics: Simulated Annealing and Tabu Search

Lesson 20 (2nd December 2022)

Laboratory on exchange metaheuristics

Lesson 21 (15th December 2022)

Recombination metaheuristics: Scatter search and Path Relinking

Lessons 22 (16th December 2022)

Recombination metaheuristics: genetic algorithms (1)

Lesson 23 (12th January 2023)

Recombination metaheuristics: genetic algorithms (2)

Lesson 24 (13th January 2023)

Laboratory on recombination metaheuristics