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

[Christian Schulte]

Hi Martin,

Please try the sketch that should work just fine and that's what I meant in
the first place...

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: Tuesday, January 29, 2013 12:08 PM
To: Guido Tack
Cc: gecode user list
Subject: Re: [gecode-users] splitting branching in full enumeration and
first-fail check

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
>

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users