Site

Preference-based Optimization For Compromise Search

When preference information is rich enough to construct a decision model refining Pareto dominance, there is no need to determine the entire set of Pareto optimal elements, but only specific compromise solutions within this set. Two main types of preference models can be distinguished:

  • (D) dominance concepts refining Pareto dominance (that induce a partial preorder on solutions)
  • (U) utility functions refining Pareto dominance (that induce a complete preorder on solutions)

We want to develop operational solution algorithms able to handle sophisticated preference models of type (D) and (U). For this purpose, two types of algorithms can be studied:
- Two-stage exploration: the first stage consists in computing the set of Pareto optimal solutions, or an approximation. The second stage consists in scanning the set obtained after stage 1 so as to determine the most appealing solution(s) according to the preference model.
- Direct preference-based search. The search is directly focused on best compromise solutions according to the preference model. This makes it possible to speed up response times and to reduce memory space requirements in the computation phase.

Task 5 will be decomposed into three complementary subtasks.

Subtask 5.1: Designing two-stage algorithms
This subtask aims at designing two-stage algorithms for preference models of type (D) and (U) that have been developed in decision theory. Since preference models are compatible with Pareto dominance, candidates to optimality must be sought within the Pareto set. Hence results obtained in Tasks 3 will have a direct impact on this activity. Approximate two-stage algorithms will also be studied. The main issue is to check whether choosing the preferred solution within an approximation of the Pareto set provides any guarantee on the approximation of the preferred solutions.

Subtask 5.2: Designing direct preference-based search algorithms
The objective of the second subtask is to design algorithms directly focusing on optimal solutions. To this end, we will investigate lower bounding procedures. For models of type (U), we will have to find efficiently computable lower bounds depending on utility function and the type of compromise sought. For models of type (D), we will have to find efficiently computable bounding sets according to the considered dominance concept. This will allow us to provide efficient implicit enumeration algorithms that explore the solution space either by branching or by ranking. We might also investigate the elaboration of approximate algorithms for preference-based optimization.

Subtask 5.3: Handling additional complexity factors
Several problems involving additional complexity factors will be studied such as problems involving different utility functions on each component Xi of the feasible set X, repeated optimization problems (the issue is then to design algorithms able to take into account mixed strategies, i.e. strategies where one chooses different solutions at each iteration), or problems involving multiple selfish agents (the issue is then to find mechanisms yielding solutions that are globally satisfying).