On 29/01/2019 16:13, ISTENC TARHAN wrote: > 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? Sorry for the very late reply... You are right, with the "restart" strategy you re-solve _almost_ the original problem, i.e. the original problem with a tighter cost bound. As you say, intuitively it seems that it should be possible to avoid duplicated work by using information from the previous search steps. However, this is not as simple as restarting with reduced domains: excluding parts of a search tree requires more complex representations, known as nogoods, which are difficult to implement efficiently. Fortunately, the cost bound is usually sufficient. Clearly, it ensures that the previous solution(s) will not be found again. And, via constraint propagation, the reduced domain of the cost variable will automatically reduce domains of other problem variables, and thus cut down the search space further. Having said that, the bb_min/3 predicate also supports a "continue" strategy, where the search is not restarted, but continues via failure in the same search tree (the tightened cost bound is then dynamically imposed for the remainder of the search). Surprisingly, this method is not always superior, essentially because restarting allows the search to be better tailored for the tighter problem. It is also less suitable for the kind of heuristic technique that you were envisaging. Cheers, Joachim > > 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-usersReceived on Fri Feb 08 2019 - 00:51:57 CET
This archive was generated by hypermail 2.3.0 : Tue Apr 16 2024 - 09:13:20 CEST