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

From: Chris Mears <chris.mears_at_monash.edu>
Date: Wed, 13 Jul 2011 15:50:41 +1000
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?

Consider a program with no constraints, and the cost to be minimized
is equal to the maximum value taken by any variable. The variables are
labeled in order, and the values are tried in random order, and the
first solution is (3,5,2), so the cost is 5. The search then
immediately backtracks to X2, apparently ignoring all the other
choices of X3. I expected it instead to at least backtrack over the
choice of X3=2.

The example program and its output are below.

Thanks,
Chris

[](_245{1 .. 5}, _259{1 .. 5}, _273{1 .. 5})
X1 = 3
X2 = 5
X3 = 2
Found a solution with cost 5
Undoing X2 = 5       <---- *** no undoing of X3=2? ***
X2 = 1
X3 = 4
Found a solution with cost 4
Undoing X3 = 4
X3 = 2
Found a solution with cost 3
Undoing X1 = 3
X1 = 2
X2 = 1
X3 = 1
Found a solution with cost 2
Undoing X1 = 2
X1 = 1
X2 = 1
X3 = 1
Found a solution with cost 1
[](1, 1, 1)


:- lib(ic).
:- lib(branch_and_bound).
:- lib(lists).

go :-
        dim(X,[3]),
        X #:: 1..5,
        C #= max(X),
        bb_min(do_search(X), C, _),
        writeln(X).

do_search(Xs) :-
        writeln(Xs),
        ( foreacharg(X, Xs, I) do
          get_domain_as_list(X, Values),
          shuffle(Values, ValuesR),
          member(V, ValuesR),
          (
            X = V,
            printf("X%d = %d\n", [I,V])
          ;
            printf("Undoing X%d = %d\n", [I,V]),
            fail
          )
        ).
Received on Wed Jul 13 2011 - 05:51:32 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET