Content deleted Content added
→Branch and bound: first-choice and russian dolls |
bucket elimination |
||
Line 24:
In particular, the cost estimate of a solution having <math>x_{i+1},\ldots,x_n</math> as unassigned variables is added to the cost that derives from the evaluated variables. Virtually, this corresponds on ignoring the evaluated variables and solving the problem on the unassigned ones, except that the latter problem has already been solved. More precisely, the cost of soft constraints containing both assigned and unassigned variables is estimated as above (or using an arbitrary other method); the cost of soft constraints containing only unassigned variables is instead estimated using the optimal solution of the corresponding problem, which is already known at this point.
==Bucket elimination==
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>
==Reference==
| |||