From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>

Date: Thu, 01 Apr 2010 17:03:39 +1100

Date: Thu, 01 Apr 2010 17:03:39 +1100

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. -- JoachimReceived on Thu Apr 01 2010 - 06:02:17 CEST

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