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

[Christian Schulte]

Hi Dirk,

 

Hmm, if it is as you say that’s surprising: you say that you create a new BAB engine. That engine would restart from whatever you give it as space, so it will start from the last solution. So that should in fact work… Why do you think it starts from scratch? >From what I understand you do not even have to modify the engine, changing the constrain() function is enough, right?

 

Don’t look at the parallel stuff that’s awful ;-) 

 

Cheers

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: Tuesday, May 9, 2017 20:43
To: Christian Schulte
Cc: users at gecode.org
Subject: Re: [gecode-users] Adding constraints to model in <RBS>: is there any example code?

 

Hi Christian,

 

sorry for taking long to respond. I read the manual and tried to modify the engines to do what I wanted. Unfortunately, I was not succesfull...

 

My first attempt was to run BAB until completion with the long steps (adding chunks of constraints in the constrain() function). I was then hoping that I should be able to modify the last solution returned by BAB (by setting a parameter in the corresponding object, lastSolution->setLargeChunks(false), to influence the behavior of the constrain function in the future), and create and run a new BAB with this solution object as initial object. (something like BAB<...> e(lastSolution, options) ). Although it does run, I get the feeling that it starts the search from the beginning and does not benefit from the search done so far. 

 

I then tried to understand how to modify the parallel engine code, but it was beyond my capabilities...

 

Thanks,

Dirk

 

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

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, cschulte at kth.se

Expert Researcher, RISE SICS, 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/20170511/a235acf9/attachment-0001.html>