[gecode-users] Adding constraints to model in <RBS>: is there any example code?

[Dirk Obermann]

Thanks, Christian.

You were, of course, correct. BAB does the job and my code is now much more
elegant than before. It also works well to combine with RBS.

However, my earlier code was sometimes faster. The reason is that I could
take "large steps", adding constraints in chunks until the search failed. I
 could then go back to the last feasible model and add constraints one by
one instead of in chunks.

Is something similar possible in the gecode search engines? What I would
like do is  the following: I run BAB until fail, and then "reset the state
of the engine" to where it was when it produced the last feasible solution
("before my last call to the constrain function", so to speak). I would
then re-run the search from there (with another behavior of the constrain
function).

Thanks,
Dirk

On Tue, Apr 11, 2017 at 1:49 PM, Christian Schulte <cschulte at kth.se> wrote:

> Hi,
>
>
>
> First, I am not so sure that your idea works in principle: you say that
> the problem is that you spend a lot of time to find a first feasible
> solution, especially after adding additional constraints. However, that
> would not change with restarts: after all, you would restart the search and
> would have to do the same search in order to find the first feasible
> solution. The only benefit I could see is adding no-goods from restarts.
>
>
>
> Anyway, what you want to do (I guess) is that you accumulate additional
> constraints which each restart. This you can only do by adding constraints
> to the master (remember, the slave will always be initialized fresh from
> the master for each restart). LNS is different as you want try different
> constraints each time you restart, hence you have to do it on the slave.
>
>
>
> Hence, you will have to reimplement the master function, there you just
> add the additional constraints.
>
>
>
> Have you thought about using BAB? There, each time you find a solution you
> can add new constraints based on that solution _*without*_ restarting
> search. Sounds more like it to me.
>
>
>
> Cheers
>
> Christian
>
>
>
> --
>
> Christian Schulte, www.gecode.org/~schulte
>
> Professor of Computer Science, KTH, cschulte at kth.se
>
> Expert Researcher, RISE SICS, christian.schulte at ri.se
>
>
>
> *From:* users-bounces at gecode.org [mailto:users-bounces at gecode.org] *On
> Behalf Of *Dirk Obermann
> *Sent:* Tuesday, April 11, 2017 13:34
> *To:* users at gecode.org
> *Subject:* [gecode-users] Adding constraints to model in <RBS>: is there
> any example code?
>
>
>
> Hello -
>
>
>
> I am trying to do program up a search engine that performs sequential
> refinement by adding more and more constraints to a model. In the first
> run, I am happy with a solution at all, but then I want to add increasingly
> complex constraints until there is no more solution (or the search engine
> times out).
>
>
>
> Now, I first run a model with a single constraint. If DFS can find a
> solution, then I run a completely new model with two constraints and from
> scratch. If this model is feasible, then I run the model with three
> constraints, etc.
>
>
>
> In principle, this solution works, but it is a very inefficient: a lot of
> time is spent generating the first feasible solution when restarting the
> search (especially as the problem becomes more constrained).
>
>
>
> It seems to me that this should be doable with RBS or a variation of the
> LDS engine, as described in the MPG. But there are very few examples to
> follow (the closest I found was this question posted on stack overflow
> http://stackoverflow.com/questions/34182681/how-to-
> change-the-variable-value-ordering-in-gecodes-restart-based-search but
> unfortunately it does not contain any answer). I simply cannot understand
> how to do it right. In particular, where do I post additional constraint on
> the model (in the master space, the slave space or elsewhere)?
>
>
>
> Any leads on how to do it, or links to code that adds constraints or
> changes branching order in RBS would be appreciated!
>
>
>
> Cheers,
>
>
>
> Dirk
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20170412/b031a4a0/attachment.html>