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

[Martin Mann]

Hi Guido,

mhh... that was my gut feeling when reading the assign documentation. So 
it basically does not really do a search for solutions but just assigns 
the (first) variable, does propagation, continues with the remaining 
variables until all are assign or no solution is found...

no, that's not what I need. True enough.

So either I do the external handling as Christian suggested, ie. 
something like

//////////////////////////////////////
CSP p = new CSP();
   // branch on A
branch(p, p.A, INT_VAR_SIZE_MIN, INT_VAL_MIN);
Gecode::DFS<CSP> dfsA(p);
delete p;
   // get all solutions for valid A assignments
while ( CSP solA = dfsA.next() ) {
     // branch on B
   branch( solA, solA.B, INT_VAR_SIZE_MIN, INT_VAL_MIN);
   Gecode::DFS<CSP> dfsB(solA);
     // get first solution for B assignment
   if( CSP solAB = dfsB.next() ) {
     cout <<"overall solution = " <<solAB <<endl;
     delete solAB;
   }
   delete solA;
}
//////////////////////////////////////

or I am back to my first guess, ie. I have to write my own branching 
that stops after the first solution on B to fall back to the branching 
on A...

:/ what a pitty. :)  Was hopeing on something hidden in the space (as 
the branching) without much work.

But thanks for your thoughts. Helped a lot to clearify the problem.

So long,
Martin


Am 28.01.2013 22:55, schrieb 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
>