[gecode-users] IIS using undoing

[Guido Tack]

On 18 Jul 2011, at 12:03, Max Ostrowski wrote:

> Thanks for the information.
> Do you think that recomputation in this case could pay off?

I don't know.  In terms of memory, possibly.  In terms of runtime, only if the search tree is deep.

> 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.
> I can not set xb to true/false, because i want the propagation of the other constraints to be the cause that xb comes true/false.

You can't use reification to observe anything about propagation, there's no reliable notion of "cause" here.  The only thing you can observe are solutions of the problem, i.e., whether an assignment satisfies the constraints (including the reified ones) or not.  And for that it doesn't matter if the xb are labeled before or after the other variables (as Chris has pointed out).

Cheers,
Guido

> 
> 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?
> 
> Best,
> Max
> 
> 
> -------- Original-Nachricht --------
>> Datum: Mon, 18 Jul 2011 10:30:35 +0200
>> Von: Guido Tack <tack at gecode.org>
>> An: Max Ostrowski <ChaosAngel at gmx.de>
>> CC: users at gecode.org
>> Betreff: Re: [gecode-users] IIS using undoing
> 
>> Hello Max,
>> 
>> you may be able to turn this into a constraint problem that you can solve
>> using the Gecode search engines, but they are also copying the spaces under
>> the hood.  The only thing they may do different from plain copying is
>> recomputation (see Sect. 7.2 in Modeling and Programming with Gecode).  There
>> is no mechanism in Gecode to undo any changes to a variable domain.
>> 
>> Cheers,
>> Guido
>> 
>> On 18 Jul 2011, at 10:05, Max Ostrowski wrote:
>> 
>>> Hello,
>>> 
>>> i want to compute an "Irreducible Infeasible Set" (IIS) and some
>> derivatives.
>>> This means, given a set of contraints C that are infeasible i want to
>> find the source of infeasibility.
>>> I'm satisfied with a rather small (but not necessarily optimal) and fast
>> approach.
>>> A simple way of doing this would now be, trying to remove all single
>> constraints from the set C and see if it is still infeasible. If yes, we can
>> remove the constraint from the set.
>>> In Gecode i could do this using a lot of copies of the Space, always
>> posting the constraints again.
>>> Instead of posting them again i could also use reified constraints and
>> set all but one to true.
>>> But here i also have to copy the space, as i can not ? undo the setting
>> of a variable.
>>> So is there a clever way of doing this abusing the Gecode SearchEngine ?
>> (what i understood from the manual there is undoing instead of copying at
>> some points).
>>> 
>>> 
>>> 
>>> The same thing i wanna do with a similar set C and a reified constraint
>> x.
>>> I wanna find the minimal (small) subset of C that the reified constraint
>> x is still decided (true or false does not matter).
>>> 
>>> 
>>> Thanks in advance for your proposals.
>>> 
>>> Best,
>>> Max
>>> 
>>> -- 
>>> NEU: FreePhone - kostenlos mobil telefonieren!			
>>> Jetzt informieren: http://www.gmx.net/de/go/freephone
>>> 
>>> _______________________________________________
>>> Gecode users mailing list
>>> users at gecode.org
>>> https://www.gecode.org/mailman/listinfo/gecode-users
>> 
>> -- 
>> Guido Tack, http://people.cs.kuleuven.be/~guido.tack/
>> 
>> 
>> 
>> 
>> 
> 
> -- 
> NEU: FreePhone - kostenlos mobil telefonieren!			
> Jetzt informieren: http://www.gmx.net/de/go/freephone
> 
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users

-- 
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/