[gecode-users] splitting branching in full enumeration and first-fail check

[Guido Tack]

Hi guys,

just using assign after branching on A doesn't work. Assign has a very different semantics, you can only use it if you are guaranteed to find a solution using the leftmost branch.
What you need here is either the two-stage search Christian mentioned: for every solution to A, run a new search engine that finds a single solution for the rest of the variables. Or implement something like the "once" combinator. I think our radiotherapy example includes code for this.
We can't provide a generic solution very easily, because it's a combinator that modifies another search heuristic (so it would have to be "wrapped around" the existing branchers).

Cheers,
Guido

-- 
Guido Tack


On 28/01/2013, at 20:38, Christian Schulte <cschulte at kth.se> wrote:

> Yes, that should do the trick as assign only creates a single alternative
> (so there will be no branching on B).
> 
> Christian
> 
> --
> Christian Schulte, www.ict.kth.se/~cschulte/
> 
> 
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Martin Mann
> Sent: Monday, January 28, 2013 10:36 AM
> To: 'gecode user list'
> Subject: Re: [gecode-users] splitting branching in full enumeration and
> first-fail check
> 
> 
> Great! Thanks Christian!
> 
> Had a look into MPG yesterday but somehow skipped it.. Thanks for the help
> and exactly the piece of code I was looking for! :)
> 
> If I am right the following statements at the end of my Space constructor
> should do right?
> 
>   branch( *this, A, ..);
>   assign( *this, B, ..);
> 
> So the overall reported solutions should show all valid assignments for A
> but for each only one valid assignment for B, right?
> 
> Please let me know if I am wrong and thanks again for the quick help!
> 
> Cheers,
> Martin
> 
> 
> 
> Am 28.01.2013 10:00, schrieb Christian Schulte:
>> That should be easy enough: set up a search engine with branching on A.
>> Suppose you get a solution there (a space): then post the simple 
>> assignment branching on B on use a different search engine to find a
> solution there.
>> 
>> You might want to read about assignment branchings in MPG.
>> 
>> Best
>> Christian
>> 
>> --
>> Christian Schulte, www.ict.kth.se/~cschulte/
>> 
>> 
>> -----Original Message-----
>> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On 
>> Behalf Of Martin Mann
>> Sent: Sunday, January 27, 2013 12:09 PM
>> To: gecode user list
>> Subject: [gecode-users] splitting branching in full enumeration and 
>> first-fail check
>> 
>> 
>> Dear Gecoders,
>> 
>> I am working on a small problem where the CSP variables are split into 
>> two subsets A and B.
>> 
>> For set A, a full enumeration of all valid assignments is wanted while 
>> for set B a single check for a valid assignment is sufficent.
>> 
>> Some years ago with Gecode 1.3 I wrote my own branching that did the 
>> latter part.
>> Thus, first normal branch on A followed by pseudo-branching on B. The 
>> latter stopped the subsearch for B after the first solution was found 
>> such that the search in A was continued and so on.
>> 
>> So my question: is there a direct support for such a scheme in Gecode 3.7?
>> Or do I have to find my old branching implementation and make it ready 
>> for the new version? I am crossing fingers you have something ready.. 
>> :/
>> 
>> Thanks for your help,
>> Martin
> 
> 
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
> 
> 
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users