[gecode-users] IIS using undoing

[Guido Tack]

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/