[gecode-users] Problem to formulate a constraint
Guido Tack
tack at gecode.org
Tue May 28 22:37:07 CEST 2013
Hi,
yes, you should channel your c_a and c_b arrays to BoolVars, then you can simply post the constraints directly using the minimodel abstractions:
BoolVarArgs b_a(...);
channel(home, b_a, c_a);
BoolVarArgs b_b(...);
channel(home, b_b, c_b);
for (int j=0; j<n; j++) {
rel(home, b_a[j] == (x[j+0] == 1));
rel(home, b_a[j] == (x[j+1] == 2));
...
}
Cheers,
Guido
--
Guido Tack
http://www.csse.monash.edu/~guidot/
On 26/05/2013, at 10:06 PM, Uwe Nowak <uwe.nowak at itwm.fraunhofer.de> wrote:
> Hi!
>
> Sorry for spamming the mailing list...
> At the moment I am focussing on the 3rd ide of modelling.
> Then I have to formulate constraints as
>
> c=j <==> x_{j+u} = v
>
> By substituting i=j-u I get
>
> c=i+u <==> x_i = v
>
> Which looks pretty much like the channel constraint, except that on the right side there is x_i = v instead of x_i = 1.
> Do I need additional (temporary) boolean variables to get rid of this?
>
> Best Regards,
> Uwe Nowak
>
>
> ----------------ursprüngliche Nachricht-----------------
> Von: "Uwe Nowak" uwe.nowak at itwm.fraunhofer.de
> An: users at gecode.org
> Datum: Sat, 25 May 2013 23:33:18 +0200
> -------------------------------------------------
>
>
>> Hi!
>>
>> Thank you for your answer. As I stated, I am a beginner to gecode and constraint
>> programming at all. I did not
>> try reification, but by this keyword I managed to solve the problem.
>>
>>
>>
>> However, I still think, that I am formulating my constraint in a bad way. I managed
>> to reduce my
>> (sub)problem to the following:
>>
>> I have an one-dimensional array
>> #############
>>
>> Furthermore, I have patterns such as
>> Pattern 1 = aa#a
>> Pattern 2 = b#b#b
>> where the hash means an empty field.
>>
>> I want to place these patterns on the array, i.e. possible placements are
>> Placement 1: aa#a###b#b#b#
>> Placement 2: aabab#b######
>>
>> No I want to store the position (i.e. the column) of each pattern in an IntVarArray
>> c, i.e. in Placement 1 it
>> is c=(0; 7) in Placement 2 it is c=(0; 2). However I do not know, how to formulate the
>> non-overlapping.
>>
>>
>> I have three possible Ideas:
>> 1. For each pattern I have an BoolVarArray to indicate if the pattern is placed
>> there
>> For Placement 1 I have two arrays (for pattern 1 = 1101000000000) and (for Pattern
>> 2 = 0000000101010)
>> Then I have constraints
>> c_a=j <==> x_{j+0} = x_{j+1} = x_{j+3} = 1
>> c_b=j <==> y_{j+0} = y_{j+2} = y_{j+4} = 1
>>
>>
>> 2. I have one IntVarArray that stores the pattern placed at this field.
>> For Placement 1 this is 1101000202020
>> Then I have constraints
>> c_a=j <==> x_{j+0} = x_{j+1} = x_{j+3} = 1
>> c_b=j <==> x_{j+0} = x_{j+2} = x_{j+4} = 2
>>
>>
>> 3. I assign different numbers to each point of the the pattern, I.e. pattern 1 =
>> 12#3 and Pattern 2=4#5#6
>> For Placement 1 this is 1203000405060
>> Then I have constraints
>> c_a=j <==> x_{j+0} = 1
>> c_a=j <==> x_{j+1} = 2
>> c_a=j <==> x_{j+3} = 3
>> c_b=j <==> x_{j+0} = 4
>> c_b=j <==> x_{j+2} = 5
>> c_b=j <==> x_{j+4} = 6
>>
>> However I am somehow lost, how to formulate such constraints efficiently.
>> Although this seems a little bit similar to the Pentomino example, with my
>> current gecode-skills I am not
>> able to transfer the Ideas.
>>
>> Best Regards,
>> Uwe
>>
>>
>> ----------------ursprüngliche Nachricht-----------------
>> Von: "Christian Schulte" cschulte at kth.se
>> An: "'Uwe Nowak'" uwe.nowak at itwm.fraunhofer.de , users at gecode.org
>> Datum: Thu, 23 May 2013 17:49:07 +0200
>> -------------------------------------------------
>>
>>
>>> Hi,
>>>
>>> Did you try reification? While not great, it should not be too hard to pull
>>> this off. Or am I missing something here?
>>>
>>> Best
>>> Christian
>>>
>>> --
>>> Christian Schulte, Professor of Computer Science, KTH,
>>> www.ict.kth.se/~cschulte/
>>>
>>>
>>> -----Original Message-----
>>> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org ] On
>>> Behalf
>>> Of Uwe Nowak
>>> Sent: Thursday, May 23, 2013 3:40 PM
>>> To: users at gecode.org
>>> Subject: [gecode-users] Problem to formulate a constraint
>>>
>>> I am a beginner with gecode and have a problem to formulate a constraint.
>>> I was looking through all channel constraints, however they do not seem to
>>> fit my needs, or I am unable to formulate my needs in the language of the
>>> channel constraints.
>>>
>>> I have the following variables
>>> *an IntVar c with a finite set of values {A_1,...,A_n} *an IntVarArray p
>>>
>>> I have the following fixed parameters
>>> For each value A_t I have a finite set of fixed indexed values I_t (e.g, an
>>> std::set<int>)
>>> A constant B
>>>
>>> Now I want to formulate the following constraints for(t = 1...n){
>>> c=A_t ==> for all I in I_t: p[i]=B
>>> }
>>>
>>>
>>> I thought to create an IntVarArgs of the subset of p with the indices I_t
>>> However, than I have tor formulated for an IntVarArgs q_t:
>>> for(t = 1...n){
>>> c=A_t ==> For all elements q_t[i]=B
>>> }
>>>
>>> However, I do not find the right expressions to formulate this in gecode...
>>>
>>>
>>>
>>> _______________________________________________
>>> Gecode users mailing list
>>> users at gecode.org
>>> https://www.gecode.org/mailman/listinfo/gecode-users
>>>
>>>
>>
>>
>> _______________________________________________
>> Gecode users mailing list
>> users at gecode.org
>> https://www.gecode.org/mailman/listinfo/gecode-users
>>
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130529/df4d4df9/attachment.html>
More information about the users
mailing list