[gecode-users] IIS using undoing

[Max Ostrowski]

Thanks again.
Last question according to this.
I finally only need a linear amount of calls to the status function of the space, but as trailsize can be huge i want to avoid overhead.
So consider i have a space with the reified constraints posted.
Lets call this the initial Space.

Now i do a copy of the initial Space setting all constraints b_1 ... b_n-1 to true. Calling status i can see if my constraint x is propagated or not.
If yes, i do not need to consider the constraint b_n anymore.

Now, in the next step, i do a copy of the initial Space setting all constraints b_1 ... b_n-2 to true. Calling statis i can see if my constraint x is propagated or not.
If yes, i do not need to consider the constraint b_n-1 anymore.
...
...

This means i need a linear amount of copies of the space (not at the same time but successively).
Can i somehow reuse parts of the propagation?
So, let n=150000, a lot of the propagation could be reused if it does not affect the constraint b_n-2.
So is there a possibility in Gecode that does (similar) things?

Best,
Max



-------- Original-Nachricht --------
> Datum: Mon, 18 Jul 2011 12:54:24 +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

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

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