P, IT (P) denotes the set of all incomplete tuples in P. When there are no incomplete tuples, we will denote a fuzzy constraint problem by FSCP.

Given an IFCSP P, a *completion of* P is an IFCSP P
′ obtained from P by associating to each incomplete tuple in every constraint an element in [0, 1]. A completion is *partial* if some preference remains unspecified. C(P) denotes the set of all possible completions of P and P C(P) denotes the set of all its partial completions.

Given an assignment s to all the variables of an IFCSP P, pref(**P, s**) is the preference of s in P, defined as pref(**P, s**) = min<idef,con>∈C|**idef**(s↓con)6=?idef(s↓con).

It is obtained by taking the minimum among the known preferences associated to the projections of the assignment, that is, of the appropriated sub-tuples in the constraints.

In the fuzzy context, a complete assignment of values to all the variables is an optimal solution if its preference is maximal. The optimality notion of FCSPs is generalized to IFCSPs via the notions of *necessarily and possibly optimal solutions*, that is, complete assignments which are maximal in all or some completions. Given an IFCSP P,
we denote by NOS(P) (resp., **P OS**(P)) the set of necessarily (resp., possibly) optimal solutions of P. Notice that NOS(P) ⊆ **P OS**(P). Moreover, while **P OS**(P) is never empty, NOS(P) may be empty. In particular, NOS(P) is empty whenever the revealed preferences do not fix the relationship between one assignment and all others.

In [7] an algorithm is proposed to find a necessarily optimal solution of an IFCSP
based on a characterization of NOS(P) and **P OS**(P). This characterization uses the preferences of the optimal solutions of two special completions of P, namely the 0completion of P, denoted by P0, obtained from P by associating preference 0 to each tuple of IT (P), and the 1-completion of P, denoted by P1, obtained from P by associating preference 1 to each tuple of IT (P). Notice that, by monotonicity of min, we have that pref0 ≤ **pref**1. When pref0 = pref1, NOS(P) = Opt(P0); thus, any optimal solution of P0 is a necessary optimal solution. Otherwise, NOS(P) is empty and **P OS**(P) is a set of solutions with preference between **pref**0 and **pref**1 in P1. The algorithm proposed in [7] finds a necessarily optimal solution of the given IFCSP by interleaving the computation of **pref**0 and **pref**1 with preference elicitation steps, until the two values coincide. Moreover, the preference elicitation is guided by the fact that only solutions in **P OS**(P) can become necessarily optimal. Thus, the algorithm only elicits preferences related to optimal solutions of P1.

## 3 A General Solver Scheme

We now propose a more general schema for solving IFCSPs based on interleaving branch and bound (BB) search with elicitation. This schema generalizes the concrete solver presented in [7], but has several other instantiations that we will consider and compare experimentally in this paper. The scheme uses branch and bound. This considers the variables in some order, choosing a value for each variable, and pruning branches based on an upper bound (assuming the goal is to maximize) on the preference value of any completion of the current partial assignment. To deal with missing preferences, branch and bound is applied to both the 0-completion and the 1-completion of the problem. If they have the same solution, this is a necessarily optimal solution and we can