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 <[email protected]> > An: Max Ostrowski <[email protected]> > CC: [email protected] > 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 <[email protected]> > >> An: Max Ostrowski <[email protected]> > >> CC: [email protected] > >> 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 > >>> [email protected] > >>> 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 > > [email protected] > > 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 [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
