[gecode-users] IIS using undoing

[Max Ostrowski]

> Betreff: Re: [gecode-users] IIS using undoing
> 

> Thanks for the information.
> Do you think that recomputation in this case could pay off?
> Furthmore, to turn it into a constraint problem, how could i configure my search in a way that the reified constraint xb==x becomes true/false, without labeling xb.

Don't try to do that. You should always aim to branch on all the variables.

You could put them at the end of the variable ordering, where they should already be assigned. Also, it might well be that allowing them to be branched on early might produce the smallest searches, it is worth exploring the possibilities.

Chris

Sorry but you got me wrong.
I will elaborate a bit more this:
Consider decision machine (outside of Gecode).
It goes stepwise:
At first it decides to make
b_3=true
then i do propagation, nothing happens
Then it decides
b_1=false
propagation -> nothing
then it sets
b_4=true
propagation -> b_2=true is propagated


Now, the simplest reason for this propagation was:
b_3 /\ -b_1 /\ b_4 -> b_2
But maybe the constraint -b_1 was not necessary for this propagation, it is about some other problem.
So maybe only given b_3=true and b_4=true would also made the propagation b_2=true.
This is only a subset and a much smarter reason for the propagation.
If i would only test b_3=true nothing would be propagated, so b_3 is not the reason for b_2.

If i would now branch on b_2 the result of the propagation would always be
satisfiable, but i could not read information out of it.
I could not find out if the tested subset is enough to decided wether b_2=true or not.

I hope i could clarify the problem a bit.

Best,
Max

>My first idea was double reification.
>Consider the reified constraint set B=C are the set to minimize so that >they still propagate x.
>I do know the values of B.
>I could post the constraints D=C with fresh boolean variables D.
>Adding then boolean reified constraints (val(B)==D)==F.
>So that F_i indicates that the constraint c_i has the predifined value(or not).
>I could then minimize on the number of true F's(branching on F).
>But i do not know how to ensure that x==xb will be decided.

Any ideas?
-- 
NEU: FreePhone - kostenlos mobil telefonieren!			
Jetzt informieren: http://www.gmx.net/de/go/freephone