Content deleted Content added
branch and bound |
→Branch and bound: first-choice and russian dolls |
||
Line 15:
On the other hand, this estimated cost cannot be lower than the effective cost that can be obtained by extending the solution, as otherwise the algorithm could backtrack while a solution better than the best found so far exists. As a result, the algorithm requires an upper bound on the cost that can be obtained from extending a partial solution, and this upper bound should be as small as possible.
===First-choice bounding functions===
One way for evaluating this upper bound for a partial solution is to consider each soft constraint separately. For each soft constraint, the maximal possible value for any assignment to the unassigned variables is assumed. The sum of these values is an upper bound because the soft constraints cannot assume an higer value. It is exact because the maximal values of soft constraints may derive from different evaluations: a soft constraint may be maximal for <math>x=a</math> while another constraint is maximal for <math>x=b</math>.
===Russian-doll search===
This method runs a branch-and-bound algorithm on <math>n</math> problems, where <math>n</math> is the number of variables. Each such problem is the subproblem obtained by dropping a sequence of variables <math>x_1,\ldots,x_i</math> from the original problem, along with the constraints containing them. After the problem on variables <math>x_{i+1},\ldots,x_n</math> is solved, its optimal cost can be used as an upper bound while solving the other problems,
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.
==Reference==
| |||