Studiegids

nl en

Multicriteria Optimization and Decision Analysis

Vak
2019-2020

Admission requirements

Not applicable.

Description

Multicriteria Optimization and Decision Analysis (MODA) deals with the various aspects of finding optimal decisions or solutions in problems with multiple decision alternatives and conflicting objectives. Thematically the topic is very close to Operational Research, Numerical Optimization, and Decision Theory.
MODA has applications in various fields of technology, scheduling, economics, environmental sciences, and life science (e.g., drug design and medical treatment). Recently, it is also used increasingly to in modern machine learning technologies.
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.

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. Understand basic terminology and modelling techniques in operational research.

  • Comprehend the axiomatic foundations of (partial) 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 can be modeled by means of polyhedral cones.

  • 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 aggregation methods, with their pros and cons, and apply basic heuristic algorithms for computing optimal point sets, such as SMS-EMOA, NSGA-II, epsilon-constraint methods, and numerical continuation.

  • Understand and be able to apply methods in multicriteria decision making in practice in real world problem domains.

Timetable

The most recent timetable can be found at the students' website.

Mode of instruction

  • Lectures

  • Exercises with solutions (non-graded)

  • Two homework assignment (graded)

Course load

Hours of study: 168 hrs. (= 6 EC)
Lectures: 33:00 hrs.
Practical work: 16:00 hrs.
Tutoring: 6:00 hrs.
Examination: 3:00 hrs.
Other (self-study): 110:00 hrs.

Assessment method

  • Exam (written), 3 hours.

  • Graded assignment on theory (10%)

  • Graded assignment on practical aspects (10%)

The final grade is composed of:

  • Two graded assignments A1 and A2 (not mandatory, but recommended) & Written Exam.

  • Final Grade = (0.1GradeA1 + 0.1 GradeA2) + 0.1 (10 - 0.1 GradeA1 - 0.1 GradeA2) * Grade Written Exam.

  • The assignments are not mandatory, but it is possible to improve the grade by doing them. Moreover, they will be good practice for the exam.

  • Grade of exam must be greater or equal to 6.

Reading list

Mandatory:

  • Michael Emmerich and André Deutz: Multicriteria Optimization and Decision Making: Principles, Algorithms, and Applications, LIACS, 2017 (Course Lecture nodes, will be made available on Blackboard)
    A compact version is given by:
    Emmerich, Michael TM, and André H. Deutz. "A tutorial on multiobjective optimization: fundamentals and evolutionary methods." Natural computing 17.3 (2018): 585-609. (open access)
    https://link.springer.com/article/10.1007/s11047-018-9685-y
    The selection of topics will be based on the slides that will be published on Blackboard.

  • 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 courses and exams (including retakes) in uSis. Check this link for information about how to register for courses.

  • Please also register for the course in Blackboard.

Contact information

Lecturer: dr. Michael Emmerich