If When=node, preferences are elicited every time a new value is assigned to a variable and it is handled by procedure Elicit@**node**. The tuples to be considered for elicitation are those involving the value which has just been assigned and belonging to constraints between the current variable and already instantiated variables. If What=all, the user is asked to provide the preferences of all the incomplete tuples involving the new assignment. Otherwise if What=worst, the user provides only the preference of the worst tuple.

BBE (P,nInstV ar, W ho, W hat, W hen, sol, lb)
sol′ ← sol, **pref**′ ← lb currentV ar ← **nextV ariable**(P1) While (nextV alue(**currentV ar, W ho**))
If (W hen = **node**)
P, pref ← Elicit@Node(**W hat, P, currentV ar, lb**)
ub ← U pperBound(P1**, currentV ar**)
If (**ub > lb**)
If (nInstvar = **number of variables in P**)
If (W hen = **branch**)
P, pref ← Elicit@branch(**W hat, P, lb**)
If (**pref > lb**)
sol ← **getSolution**(P1) lb ← pref(P1**, sol**)
else BBE(**P, nInstV ar** + 1**, W ho,W hat,W hen, sol, lb**)
If (W hen=**tree and nInstV ar** = 0)
If(sol = nil)
sol ← sol′, pref ← **pref**′
else P, pref ← Elicit@tree(**W hat, P, sol, lb**)
If(**pref > pref**′)
BBE(P, 0**, W ho,W hat,W hen, sol, pref**)
else BBE(P, 0, W ho, W hat,W hen, sol′**, pref**′)
Fig. 3. Algorithm BBE.

Theorem 1. Given an IFCSP P *and a consistent set of values for parameters When,*
What and Who, Algorithm IFCSP-SCHEME *always terminates, and returns an IFCSP*
Q ∈ P C(P)*, an assignment* s ∈ NOS(Q)*, and its preference in* Q.

Proof. Let us first notice that, as far as correctness and termination concern, the value of parameter Who is irrelevant.

We consider two separate cases, i.e., When=tree and and When=branch or node. Case 1: When =tree.

Clearly IFCSP-SCHEME terminates if and only if BBE terminates. If we consider the pseudocode of procedure BBE shown in Algorithm 3, we see that if When = tree, BBE