Re: [eclipse-users] Question about branch and bound

Dimitris Bilidas wrote:
> Hello all, 
> 
> I am a little confused, so sorry if my question is somehow naive or something.
> 
> Let's say that we have the problem of the N-queens as it is solved here
> http://eclipse.crosscoreop.com/examples/queens.ecl.txt 
> in which additionally every solution has a specific cost.  So we have changed
> the labeling predicate with one more variable Cost in which we assign the
> numeric value of the cost for every solution. For example:
> labeling(a, AllVars, BT, Cost) :-
>         search(AllVars, 0, input_order, indomain, complete, [backtrack(BT)]),
>         computeCost(AllVars, Cost).
> 
> 
> Now we call this like that:
> branch_and_bound:minimize(labeling(Strategy, Board, BT, Cost), Cost)
> 
> If we write something like that, will we have any pruning at all? From what I
> have understood no, because the cost is being computed only after a final
> solution has been found. So what should we do if we wanted to start pruning
> possible solutions earlier?

You are right, you won't get any pruning if you write it like that.
That's why you should express the cost in terms of a constraint,
and do it before starting the search, i.e.

    ...
    Cost #= ...,
    branch_and_bound:minimize(labeling(Board), Cost).

E.g. to minimize the distance between adjacent queens:

    ...,
    ( fromto(Board, [Qi,Qj|Qs], [Qj|Qs], [_Qn]), foreach(D,Ds) do
        D #= abs(Qi-Qj)
    ),
    Cost #= sum(Ds),
    branch_and_bound:minimize(labeling(Board), Cost).


-- Joachim