Heuristic and Approximation Algorithms are Operational Research tools that provide solutions to real-world optimisation problems across a wide range of application areas despite their inherent complexity and uncertainty. Heuristic algorithms include a range of techniques from simple ‘rules of thumb’ to more sophisticated methods inspired on physical and natural processes. Heuristics can provide good-quality solutions (though not necessarily optimal) in practical computational time to otherwise intractable problems. Approximation algorithms are designed to guarantee solutions of given quality based on worst-case analysis. The course features the main techniques for heuristic and approximation algorithms as well as an insight into data science and machine learning in the context of heuristic optimisation. The course is delivered by a set of experts in the field with strong publication records and experience in the design and deployment of these methods on real-world problems.

PRE-REQUISITES

Basics of complexity and optimization theory as well as computer algorithms. Some reading material is provided to students a few weeks in advance to the start of the course.

AIM

On completion of the course, students should have a working knowledge of the theory, design, implementation and applications of the main heuristic methods and approximation algorithms, as well as an insight into their interplay with data science and machine learning in the context of optimisation scenarios.

LEARNING OUTCOMES

– Understanding of the fundamental theory underlying approximation algorithms and the main heuristic optimisation methods (e.g. local search, metaheuristics, hyper-heuristics, evolutionary algorithms, etc.).

– Awareness of the strengths and limitations of different heuristic optimisation methods.

– Ability to critically evaluate the applicability and quality of different heuristic optimisation methods.

– Capability for designing and developing appropriate heuristic methods to different optimisation problems.

– Awareness of existing software tools for the rapid prototyping of heuristic optimisation methods.

– Understanding of the fundamentals of data science and machine learning in the context of heuristic optimisation.

TOPICS COVERED

Introduction to Optimization, Complexity Theory, Approximation Algorithms, Local Search, Meta-heuristics, Multi-objective Heuristics, Hyper-heuristics, Evolutionary Algorithms, Hybrid Heuristics, Big Data and Machine Learning.

ASSESSMENT

A few formative assessments throughout the course in the form of quizzes and practical exercises, in addition to a summative test at the end of the course.