[gecode-users] IIS using undoing

[Max Ostrowski]

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.
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.

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