Re: [eclipse-clp-users] bb_min search strategies

Bogdan Tanasa wrote:
> Hi,
> 
> There is any possibility to change search strategies at run-time? For
> example after a specific period of time to use restart strategy instead of
> continue?

Yes, you can do that by using timeouts and invoking several bb_min's
in sequence.  Because you are not interested in the suboptimal solutions
that you get from timed-out bb_min calls, you need to use bb_min/6
for all but the last stage.

Example:

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

test(Xs, Cost) :-
        % example problem
        length(Xs, 10),
        Xs :: 0..100,
        alldifferent(Xs),
        Cost #= -sum(Xs),

        % minimize with dichotomic strategy for 1 second
        % resulting in best cost so far BestCost
        bb_min(labeling(Xs),
                Cost, [], [], BestCost,
                bb_options{strategy:dichotomic,timeout:1}),

        % impose the cost bound just found, and
        % minimize again with different strategy
        Cost #=< BestCost,
        bb_min(labeling(Xs),
                Cost, bb_options{timeout:4}).


?- test(Xs, Cost).
Found a solution with cost -45
Found a solution with cost -523
Found a solution with cost -762
Branch-and-bound timeout!
Found a solution with cost -762
Found a solution with cost -763
Found a solution with cost -764
Found a solution with cost -765
Found a solution with cost -766
Found a solution with cost -767
Found a solution with cost -768
Found a solution with cost -769
Found a solution with cost -770
Found a solution with cost -771
Found a solution with cost -772
Found a solution with cost -773
Found a solution with cost -774
Found a solution with cost -775
Found a solution with cost -776
Found a solution with cost -777
Branch-and-bound timeout!

Xs = [0, 5, 93, 94, 95, 96, 97, 98, 99, 100]
Cost = -777
Yes (5.00s cpu)

[ Note: in practice you will also need to think about what you
  want to do if the first or second bb_min fails. ]


The bb_min timeouts limit the _total_ time that the search takes.
It might often be more helpful to limit the time to find the _next_
solution, i.e. give up when you can't find a better solution quick
enough.  That can be done using separate timeouts with timeout/3:

:- lib(timeout).

test(Xs, Cost) :-
        % example problem
        length(Xs, 10),
        Xs :: 0..100,
        alldifferent(Xs),
        Cost #= -sum(Xs),

	bb_min(timeout(labeling(Xs), 0.2, (writeln(timeout),fail)),
                Cost,
                bb_options{strategy:dichotomic}).

?- test(X,C).
Found a solution with cost -45
Found a solution with cost -523
Found a solution with cost -762
timeout
Found no solution with cost -1000.0 .. -881.0
timeout
Found no solution with cost -881.0 .. -821.5
timeout
Found no solution with cost -821.5 .. -791.75
timeout
Found no solution with cost -791.75 .. -776.875
Found a solution with cost -770
timeout
Found no solution with cost -776.875 .. -773.4375
Found a solution with cost -772
Found a solution with cost -773

X = [0, 1, 93, 94, 95, 96, 97, 98, 99, 100]
C = -773
Yes (3.21s cpu)

[ Note: this works only with restart or dichotomic,
  because of the way 'continue' is implemented ]


> Moreover, when changing strategies is it possible for the new one to
> continue from the last solution that previous strategy had found.

Only the 'continue' strategy continues from the last solution, and
cannot start from an arbitrary solution.  Both 'restart' and
'dichotomic' strategies always restart search from the root anyway.

But all strategies can take an initial cost bound into account,
as done in the first example above.


> 
> If this thing is possible will affect the optimality of the final
> solution?

What affects the optimality is the timeouts, i.e. not exploring
the whole search tree, thereby possibly missing a better solution.


-- Joachim