Re: [eclipse-clp-users] Updating upper bound - of a minimization problem- during search

Thanks for your quit explanatory answer.

The only point I am worried about is the "Restarting the search" part.
After finding a new solution, incumbent solution is updated and search
is restarted. Yet, new search should have reduced domains of variables
due to the propagation in the previous searches, right?
Otherwise, each search would be equivalent to solving the original
problem with an updated upper bound.

If I understand correctly, wouldn't this search scheme be too time consuming?

Best,
İstenç

On Mon, Jan 21, 2019 at 2:47 PM Joachim Schimpf <jschimpf_at_...311...> wrote:
>
> On 18/01/2019 14:19, ISTENC TARHAN wrote:
> > Hello,
> >
> > I need to perform the act in the subject "Updating lower bound  - of a
> > minimization problem- during search" in my algorithm. Specifically,
> > when all variables are instantiated (i mean, at a leaf node), i want
> > to develop a new solution from it heuristically and update the upper
> > bound of the problem.
>
>
> The updating of the cost bound during minimization is typically
> handled by the branch-and-bound minimization predicate bb_min/3, see
> http://eclipseclp.org/doc/bips/lib/branch_and_bound/bb_min-3.html
>
> The basic usage is as follows: you start with a program that computes
> _all_ solutions, which usually has a structure such as
>
>      all_solutions(Xs, Cost) :-
>          constraint_model(Xs),        % deterministic constraint setup
>          Cost #= ...,                 % Cost is some function of Xs
>          labeling(Xs).                % nondeterministic search
>
> This will, on backtracking, generate every solution together with
> its cost.  [Instead of labeling/1, you could use have used search/6
> or you own search procedure.]
>
> To find a minimal solution, wrap the nondeterministic search predicate
> into bb_min/3:
>
>      :- lib(branch_and_bound).
>
>      best_solution(Xs, Cost) :-
>          constraint_model(Xs),
>          Cost #= ...,
>          bb_min(labeling(Xs), Cost, bb_options{strategy:restart}).
>
> This works as follows (I describe the 'restart' strategy here):
> 1. labeling(Xs) finds a first solution with cost Cmin
> 2. bb_min restarts the search with a cost upper bound of Cmin-1
> 3. if a better solution is found, call it Cmin and goto 2
> 4. else the last value of Cmin is the optimum Cost
>
> "Restarting the search" simply means that the whole search (propagation,
> variable bindings, etc) is undone, and labeling/1 is called again. The
> only difference is that the cost upper bound is now lower than previously.
>
>
> Now, what you wanted to do was to use a previous solution in a heuristic
> for finding another solution.  An easy way to do that is to introduce a
> "memory" that survives the undoing of the search before restart.
> In the following, I have used a "record" object
> (http://eclipseclp.org/doc/bips/kernel/record/index.html), but you could
> use any of the other non-backtrackable storage facilities described in
> http://eclipseclp.org/doc/bips/kernel/storage/index.html
>
> The Memory object is initialised before the optimization, and used to
> remember the last solution found.  Note that bb_min/3 will still take
> are of the cost bound maintenance, making sure that only improving
> solutions are found:
>
>      good_solution(Xs, Cost) :-
>          constraint_model(Xs),
>          Cost #= ...,
>          record_create(Memory),
>          bb_min((
>              ( erase(Memory, LastXs) ->
>                  % find new solution based on previous one
>                  heuristic_search(LastXs, Xs)
>              ;
>                  % no previous solution, find a first one
>                  labeling(Xs)
>              ),
>              % store the new solution vector
>              record(Memory, Xs)
>          ), Cost, bb_options{strategy:restart}).
>
> If there was no previous solution (erase/2 fails), we use some
> default method to find a starting solution.  Otherwise, we call our
> heuristic_search/2 with two vectors: a vector of values of the
> previous solution, and the corresponding vector of problem variables.
>
> By the way, a particularly simple way of implementing such a heuristic
> search is "shuffle search", where you set a random subset of the variables
> to their old solution values, and then simply let a standard labeling
> method fill in the rest.
>
> Such a heuristic approach is usually no longer a complete search:
> when heuristic_search/2 fails, it does not necessarily mean that no
> better solution exists, but only that the heuristic can't find one.
> There are again many strategies to recover from this, e.g. by trying
> to find a new, possibly randomized, starting solution.
>
> Randomized searches on huge search spaces do not usually terminate
> naturally, so you might also want to use bb_min's timeout option!
>
>
> Hope this helps,
> Joachim
>
>
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users