Our first lecture will take place on Thursday, Sep 18, 16:15-19:15 in room 1004. That is, the lecture will be held in person onsite. Remote participation will not be possible. We will share lecture materials after the lecture. Students not registered through the MPRI system are invited to contact Carola by email to obtain slides and notes. (the larger part of the first lecture will be on the black board).

This year, the course will be held on Thursdays, in the late afternoon slots, i.e., Thursdays, 16:15-19:15 in room 1004.

The first lecture is on September 18, 2025.

We offer internships on the topic of this course. Simply reach out to us if you are interested in doing your M2 internship with us.

Carola Doerr (CNRS research director, LIP6, Sorbonne Université)

• Benjamin Doerr (LIX, École Polytechnique, IPP)
• Carola Doerr (CNRS, LIP6, Sorbonne Université)

In previous years (from 2015 until 2020), the course was taught by Carola Doerr and Christoph Dürr.

Evripidis Bampis (LIP6, Sorbonne Université) is pausing in 2025/26.

This course will be held in English. Exam answers and project reports can be answered in English or French.

The current MPRI offer contains courses on different algorithmic problems, for which solutions are designed that are tailored to the problem at hand. These solutions are often exact, and their optimization times ideally (close to being) best possible. In this course we want to give a complementary view on algorithmics in computer science. We present general-purpose heuristics which are widely applied to solve real-world optimization challenges, such as local search algorithms and randomized search heuristics like Simulated Annealing and evolutionary algorithms. Our course focuses on the theoretical aspects of this area. Runtime bounds, complexity statements, and approximation ratios are rigorously proven in the course.

Some background on algorithms and probability theory (e.g., expected value, binomial distribution).

The course starts with a summary of solution techniques and problems that the students might have seen in their studies, for example local search algorithms for facility location. Then we introduce formally a few different popular heuristic approaches, such as random sampling, local search, simulated annealing, genetic algorithms. Theoretical background from both deterministic and randomized algorithm analysis will be introduced. Students will see how to apply them to show lower bounds and upper bounds on the performance of the different heuristics. Finally, we given an illustrative example, highlighting how to use insights from this course to design new efficient problem solvers.

The lecture itself will be mostly on the black board, the slide decks are not guaranteed to cover all content discussed in the course. We will share slides and possibly additional notes or references by e-mail after each lecture.

In-class exercises will help students (and the teachers ;)) identify topics that may require more discussion.

References (likely to evolve):

• Drift Analysis: survey and examples. https://arxiv.org/abs/1712.00964
• Black-Box Complexity: survey of models and results. https://arxiv.org/abs/1801.02037
• Online Parameter Selection: survey of known theoretical results: https://arxiv.org/abs/1804.05650
• Useful probabilistic tools: https://arxiv.org/abs/1801.06733

Below is a preliminary outline of the course in 2025/26.

18/09/2025 [Carola] Introduction to black-box optimization and heuristic search

25/09/2025 [Carola] Runtime analysis of randomized search heuristics, Performance evaluation of iterative search algorithms

02/10/2025 [Carola] Black-box complexity

09/10/2025 [Benjamin] Advanced runtime analysis: Drift analysis

16/10/2025 [Benjamin] Parameter optimization and control

23/10/2025 [Benjamin] Multi-objective evolutionary algorithms

30/10/2025 (no lecture, MPRI holidays)

06/11/2025 [Benjamin] Noisy optimization

13/11/2025 [Carola] Presentation of the projects by the students

20/11/2025 (no lecture)

27/11/2025 or 4/12/2025 final exam

There will be one extended homework and a final written exam. Final grading will combine these two grades.

Internships, also in collaboration with international colleagues, will be proposed during the lectures. Students interested in an internship are invited to contact the instructors for more information. We will be happy to share and discuss potential internship projects