The Swiss engineering master's degree

This module introduces students with different categories of advanced algorithms and typical application areas.
In the first part of the module, the students will have a sound understanding of data structures and algorithms for efficiently handling either very large, complex or dynamic data sets or combinations thereof. They will be able to evaluate suitable algorithms and to apply them to typical tasks such as efficiently indexing, searching, retrieving, inserting or updating data such as large volumes of hypertext or spatial data.
The students will be familiar with dynamic algorithms used, for example, in artificial intelligence.
The second part of the module will present basic techniques for designing algorithms for hard combinatorial optimization problems. The combination of these basic components —problem modeling, problem decomposition, solution building, solution improvement, learning— lead to classical metaheuristics like genetic algorithms, ant colonies or tabu search. The students will be able to design new algorithms for hard combinatorial optimization problems and to apply them.

Prerequisites

The student has working knowledge of:

• Geometry, linear algebra, algorithms (sorting, searching, hashing) and data structures (linear structures, trees)
• Basics of graph data structures and algorithms
• Algorithmic complexity, logic, probability theory.

These topics are generally contained in books introducing algorithms. For instance, chapters 1-12, 15-17, 22-26, 28-29, 34-35 of (Cormen 09) covers very well the prerequisites

Learning Objectives

This module gives the student an overview of frequently used algorithms classes. Based on this strong foundation, students can design and implement the most suitable and efficient algorithms for use in their own applications. The student:

• is familiar with different categories of advanced algorithms and with typical application areas;
• has a sound understanding of data structures and algorithms for efficiently handling either very large, complex or dynamic data sets or combinations thereof;
• is able to evaluate suitable algorithms and to apply them to typical tasks such as efficiently indexing, searching, retrieving, inserting or updating data, including data types such as large volumes of hypertext or spatial data;
• is familiar with dynamic algorithms used in robotics, artificial intelligence.

Contents of Module

Algorithms and data structures for selected practical problems. Weight 50%

• Reminder on linear structures, binary search tree, heap and algorithmic complexity
• Randomized algorithms (qsort, selection in linear time, kD tree, range tree, Delaunay triangulation)
• Deterministic algorithms(selection, kD tree)
• Sweep algorithms (closest pair of points, segment intersection)
• Greedy algorithms (Huffman code, Dijkstra, Fibonacci heap)

Design of heuristic algorithms. Weight 50%

• Reminder on complexity theory, combinatorial optimization problems, problem modelling
• Greedy heuristics
• Local search heuristics
• Decomposition methods
• Randomized heuristics
• Learning heuristics
• Classical metaheuristics: GRASP, ant colonies, tabu search, simulated annealing, noising methods, genetic algorithms

Teaching and Learning Methods

• Ex-cathedra teaching
• Presentation and discussion of case studies
• Problem-based learning
• Theory and programming exercises

Literature

M. de Berg, G. Cheong, M. van Kreveld, M. Overmars. Computational Geometry : Algorithms and Applications, Springer, Third Edition 2008.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, third edition, MIT Press, 2009.

P. Siarry (ed.), Metaheuristics, ISBN 978-3-319-45403-0, Springer, 2016.

H. H. Hoos, Th. Stützle Stochastic Local Search: Foundations and Applications, Morgan Kaufmann / Elsevier, 2004.

Éric D. Taillard

Design of Heuristic Algorithms for Hard Optimization

(Series: Graduate Texts in Operations Research)

Springer, 2023

ISSN 2662-6012

ISSN 2662-6020 (electronic)

ISBN 978-3-031-13713-6

ISBN 978-3-031-13714-3 (eBook)

doi.org/10.1007/978-3-031-13714-3

mistic.heig-vd.ch/taillard/heuristic_design/