- Mail actions: [ respond to this message ] [ mail a new topic ]
- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Joachim Schimpf <jschimpf_at_...311...>

Date: Mon, 21 Jan 2019 11:18:15 +0000

Date: Mon, 21 Jan 2019 11:18:15 +0000

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, JoachimReceived on Mon Jan 21 2019 - 11:45:07 CET

*
This archive was generated by hypermail 2.3.0
: Tue May 14 2019 - 03:13:25 CEST
*