[gecode-users] IIS using undoing

Guido Tack tack at gecode.org
Tue Jul 19 11:42:33 CEST 2011 

On 18 Jul 2011, at 13:22, Max Ostrowski wrote:

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

What you're trying to do here is the opposite of search: during search, the variables become monotonically more restricted, so the propagation is reused in that sense (you only propagate the new changes).  Your variables become monotonically less restricted (you start with all being 1, then un-assigning them one by one).  Constraint solvers are not built for this kind of anti-monotonicity, so they can't reuse the propagation (they'd have to find out which constraints are not affected by the variable you are un-assigning, which is the exact opposite of finding our which ones are affected by the new assignment).

Cheers,
Guido

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

More information about the users mailing list