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

[Christian Schulte]

Hi Dirk,

 

Yes, I see your motivation but the Gecode engines cannot do that. Have you ever had a look at the part in MPG about search? Building a BAB engine with this additional feature might be not that hard…

 

Good luck

Christian

 

--

Christian Schulte, www.gecode.org/~schulte

Professor of Computer Science, KTH,  <mailto:cschulte at kth.se> cschulte at kth.se

Expert Researcher, RISE SICS,  <mailto:christian.schulte at ri.se> christian.schulte at ri.se

 

From: Dirk Obermann [mailto:dirk.obermann67 at gmail.com] 
Sent: Wednesday, April 12, 2017 22:28
To: cschulte at kth.se
Cc: users at gecode.org
Subject: Re: [gecode-users] Adding constraints to model in <RBS>: is there any example code?

 

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> 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/20170418/0243b12b/attachment.html>