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

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