Re: [eclipse-clp-users] Branch-and-bound search continuation

Hi Chris,

Chris Mears wrote:
> Hello all,
> 
> I have a question about the behaviour of lib(branch_and_bound). When a
> solution is found, and with the default "continue" strategy, a new
> limit on the cost is imposed and the search goal resumes. Where
> exactly does it resume from?

After succeeding with a new optimal solution, the computation simply
fails and backtracks to the most recent choice point.  However, at
the beginning of every further alternative of every choice point
that existed at that time, a high priority test is woken which
immediately forces failure if the cost variable cannot assume
a value better than the best solution so far.

In your example code, this test happens both inside the member/2
predicate, and also in the second alternative of the disjunction
which you have introduced for printing your messages:

 > do_search(Xs) :-
 >         writeln(Xs),
 >         ( foreacharg(X, Xs, I) do
 >           get_domain_as_list(X, Values),
 >           shuffle(Values, ValuesR),
 >           member(V, ValuesR),      <<<< bound test here
 >           (
 >             X = V,
 >             printf("X%d = %d\n", [I,V])
 >           ;                        <<<< bound test here
 >             printf("Undoing X%d = %d\n", [I,V]),
 >             fail
 >           )
 >         ).

So, the missing branches are there, but you don't see them because
they fail immediately, before you can print anything!

To get a trace that is closer to what you expect to see, you can
use call_priority/2 to defer the bounds test a bit.  Replacing
the call to member/2 by

     call_priority(
       (member(V, ValuesR), printf("trying X%d = %d\n", [I,V])),
       2),

then gives a trace like

[](_251{1 .. 5}, _269{1 .. 5}, _287{1 .. 5})
trying X1 = 5
X1 = 5
trying X2 = 5
X2 = 5
trying X3 = 2
X3 = 2
Found a solution with cost 5
trying X3 = 4
trying X3 = 3
trying X3 = 1
trying X3 = 5
trying X2 = 4
trying X2 = 3
trying X2 = 1
trying X2 = 2
Undoing X1 = 5
trying X1 = 1
X1 = 1
trying X2 = 1
X2 = 1
trying X3 = 3
X3 = 3
Found a solution with cost 3
Undoing X3 = 3
trying X3 = 4
Undoing X3 = 4
trying X3 = 2
X3 = 2
Found a solution with cost 2
Undoing X3 = 2
trying X3 = 1
X3 = 1
Found a solution with cost 1
[](1, 1, 1)


-- Joachim