cution of IFCSP-SCHEME, sol, with preference **pref** is one of the optimal solutions of the current P1Thus, for every assignment s
′, pref(P1, s′) ≤ pref(P1**, sol**). Moreover, for every completion Q′ ∈ C(P) and for every assignment s
′, pref(Q′, s′) ≤
pref(P1, s′). Hence, for every assignment s
′and for every Q′ ∈ C(P), we have that pref(Q′, s′) ≤ pref(P1**, sol**). In order to prove that sol ∈ NOS(P), now it is sufficient to prove that for every Q′ ∈ C(P), pref(P1**, sol**) = pref(Q′**, sol**). This is true, since sol has a preference that is independent from the missing preferences of P, both when eliciting all the missing preferences, and when eliciting only the worst one either at branch or node level. In fact, in both cases, the preference of sol is the same in every completion. Q.E.D.

If When=tree, then we elicit after each BB run, and it is proven in [7] that IFCSPSCHEME never elicits preferences involved in solutions which are not possibly optimal. This is a desirable property, since only possibly optimal solutions can become necessarily optimal. However, the experiments will show that solvers satisfying such a desirable property are often out-performed in practice.

## 4 Problem Generator And Experimental Design

To test the performance of these different algorithms, we created IFCSPs using a generator which is a simple extension of the standard random model for hard constraints to soft and incomplete constraints. The generator has the following parameters:

- n: number of variables; - m: cardinality of the variable domains; - d: density, that is, the percentage of binary constraints present in the problem w.r.t.

the total number of possible binary constraints that can be defined on n variables;
- t: tightness, that is, the percentage of tuples with preference 0 in each constraint and in each domain w.r.t. the total number of tuples (m2for the constraints, since we have only binary constraints, and m in the domains);
- i: incompleteness, that is, the percentage of incomplete tuples (that is, tuples with preference ?) in each constraint and in each domain.
Given values for these parameters, we generate IFCSPs as follows. We first generate n variables and then d% of the n(n − 1)/2 possible constraints. Then, for every domain and for every constraint, we generate a random preference value in (0, 1] for each of the tuples (that are m for the domains, and m2for the constraints); we randomly set t% of these preferences to 0; and we randomly set i% of the preferences as incomplete.

Our experiments measure the *percentage of elicited preferences*(over all the missing preferences) as the generation parameters vary. Since some of the algorithm instances require the user to suggest the value for the next variable, we also show the *user's effort* in the various solvers, formally defined as the number of missing preferences the user has to consider to give the required help.

Besides the 16 instances of the scheme described above, we also considered a "baseline" algorithm that elicits preferences of randomly chosen tuples every time branch