KR Conference 2016 Short Paper
- Nicolas Schwind
- Tenda Okimoto
- Maxime Clement
- Katsumi Inoue
Solving a multi-objective constraint optimization problem (MO-COP) typically consists in computing all Pareto optimal solutions, which are exponentially many in the general case. This causes two problems: time complexity and lack of decisiveness. We present an approach which, given a number k of desired solutions, selects k Pareto optimal solutions that are representative of the Pareto front. We analyze the computational complexity of the underlying computational problem and provide exact and approximation procedures. Preliminaries We consider a given fixed number m of objectives. A multiobjective constraint optimization problem (MO-COP) is a tuple X, D, C h, C s , where: X = {x1,..., xn } is a set of variables; D = {D1,..., Dn } is a multiset of non-empty domains for the variables; C h is a finite set of hard constraints, i. e., for each Cjh ∈ C h, Cjh ⊆ Di1 × · · · × Dij for some {Di1,..., Dij } ⊆ D; and C s is a finite set of soft, polyadic constraints, i. e., each Cjs ∈ C s is a mapping from {Di1,..., Dij } to Nm, for some {Di1,..., Dij } ⊆ D. Each constraint from C h ∪ C s involves a set of variables Xj ⊆ X called its scope. Let P be an MO-COP X, D, C h, C s . An assignment A of P associates each xi ∈ X with a value from Di; A is a solution of P if there is no Cjh ∈ C h such that (A(xi1),..., A(xij)) ∈ Cjh, where {xi1,..., xij } is the scope of Cjh. Sols(P) denotes the set of solutions of P. Given an m-vector U, we denote by U k or U (k) its k th component, with k ∈ {1,..., m}. The cost vector of A is the mvector denoted defined for each k ∈ {1,..., m} as by V (A) s C (A(x V (A)k = s s i1),..., A(xij))(k), where for j Cj ∈C each Cjs, {xi1,..., xij } is the scope of Cjs. When S is a set of solutions, V (S) denotes the set {V (A) | A ∈ S}. Let m be the product ordering over Nm, i. e., ∀V1, V2 ∈ Nm, V1 m V2 iff ∀k ∈ {1,..., m}, V1k ≤ V2k. The preordering P ar over Sols(P), called the Pareto dominance relation, is defined ∀A, A ∈ Sols(P) as A P ar A iff V (A) m V (A); we say that A Pareto dominates A. A Pareto optimal solution of P is a solution S ∈ Sols(P) which is not strictly Pareto dominated by an other solution S ∈ Sols(P). SP ar (P) denotes the set of Pareto optimal solutions of P, and PF(P) = S∈SP ar (P) V (S) is called the Pareto front of P.