Admission requirements
The students should have taken a course in AI.
Description
Multicriteria Optimization and Decision Analysis (MODA) deals with the various aspects of finding optimal decisions in problems with multiple decision alternatives and conflicting objectives, which recently became a ‘hot’ topic in various fields of technology, economy and science. As opposed to single-objective optimization, in multiobjective optimization there is no single best solution. It is thus common to directly or indirectly search for a set of Pareto efficient solutions (Pareto front) and apply set-oriented search procedures for this. Besides, there is an alternative approach, which is the construction of ranking and scoring methods that aggregate objectives, which typically yields a particular efficient solution on the Pareto front. Moreover, in multicriteria decision analysis, the assessment of multivariate data and trade-offs is discussed, and tools that can supporting human decision makers in complex environments. In the first part we will discuss foundations of the field, including mathematical treatment of partial orders, cones, and domination, as well as optimality definitions that rests on these. We will also discuss the geometry of Pareto optimal sets and how ranking methods can be designed in order to express the preferences of a user. The second part of the course focuses on algorithmic aspects. We will review fundamental algorithms for optimal subset selection, as well as deterministic and stochastic methods for approximating or finding the Pareto front. A particular focus will be on hypervolume-oriented methods which recast the problem of finding all Pareto efficient solutions as a problem of finding sets as a single objective optimization problem on the space of sets. Accuracy, Efficiency, Reliability, and User-friendliness are guiding criteria in the design of multiobjective optimization algorithms. The theory of these algorithms is still under development and we will discuss very recent breakthrough results and major open problems in this field.
Dr. Michael Emmerich will teach the part on multiobjective optimization, and the part on multicriteria decision analysis will be teached by Dr. IrynaYevseyeva.
Course objectives
At the end of the class the student should be able to
formulate and identify different types of mathematical programming problems, including formulations with constraints and multiple objectives
comprehend the axiomatic foundations of orderings. Be able to compare different ordered sets and analyze their properties; understand the interpretation of ordered sets Cartesian space as a concept governed by dominance regions, which often exhibit the structure of a cone.
understand the concept of Pareto optimality, efficiency, weak efficiency and incomparibility
analytically solve simple Pareto optimization problems that are special cases for the application of Karush Kuhn Tucker conditions and the Lagrange multiplier theorem
know different scalarization methods, with their pros and cons
apply basic heuristic algorithms for computing optimal point sets, such as SMS-EMOA, NSGA-II
understand and be able to apply methods in Multicriteria decision aiding.
Timetable
The most recent timetable can be found at the LIACS website
Mode of instruction
lectures
practical assignment/project
Assessment method
Exam (written), 2h30 Minutes
Graded assignment on theory
Graded assignment on practical aspects
Two graded assignments. One Exam.
FinalGrade = (0.2 A1 + 0.2 A2) + 0.1 (10 – 0.2 A1 – 0.2 A2) * GradeExam.
(This formula rewards doing the assignments, while for those who did not do them it puts more weight on the exam grade. The exam accounts for at least 60% of the grade.)
Reading list
Mandatory:
Reader: Michael Emmerich and André Deutz: Multicriteria Optimization and Decision Making: Principles, Algorithms, and Applications, LIACS, 2012
Background literature:
- Matthias Ehrgott: Multicriteria Optimization, Springer 2005
- KaizaMiettinen: Nonlinear Multiobjective Optimization, Kluwer, 1999
- N Beume, B Naujoks, M Emmerich: SMS-EMOA: Multiobjective selection based on dominated hypervolume, European Journal of Operational Research 181 (3), 1653-1669 , 2007
- H. T. Kung, F. Luccio, and F. P. Preparata. 1975. On Finding the Maxima of a Set of Vectors. J. ACM 22, 4 (October 1975), 469-476.
Registration
You have to sign up for classes and examinations (including resits) in uSis. Check this link for more information and activity codes.
There is a limited capacity for students from outside the master Computer Science programme. Please contact the study-advisor.
Contact information
Study coordinator Computer Science, Riet Derogee