Content deleted Content added
No edit summary |
No edit summary |
||
Line 67:
The [[bucket elimination]] algorithm can be adapted for constraint optimization. A given variable can be indeed removed from the problem by replacing all soft constraints containing it with a new soft constraint. The cost of this new constraint is computed assuming a maximal value for every value of the removed variable. Formally, if <math>x</math> is the variable to be removed, <math>C_1,\ldots,C_n</math> are the soft constraints containing it, and <math>y_1,\ldots,y_m</math> are their variables except <math>x</math>, the new soft constraint is defined by:
<!-- not exactly the correct notation, but clear enough -->
:<math>C(y_1=a_1,\ldots,y_n=a_n) = \max_a \sum_i C_i(x=a,y_1=a_1,\ldots,y_n=a_n).</math>
Bucket elimination works with an (arbitrary) ordering of the variables. Every variable is associated a bucket of constraints; the bucket of a variable contains all constraints having the variable has the highest in the order. Bucket elimination proceed from the last variable to the first. For each variable, all constraints of the bucket are replaced as above to remove the variable. The resulting constraint is then placed in the appropriate bucket.
| |||