[gecode-users] Generating constraints
Max
chaosangel at gmx.de
Tue Oct 28 14:35:39 CET 2008
I have written the code for the analyzer now, but i just wanted to avoid
this code-bloating.
46 void GecodeSolver::SearchSpace::generateConstraint(CSPConstraint c,
unsigned int boolvar)
47 {
48
49 if (c.getType() == CSPConstraint::RELATION)
50 {
51 CSPConstraint* x;
52 CSPConstraint* y;
53 CSPConstraint::Relation r = c.getRelation(x,y);
54
55 IntVar r1;
56 IntVar r2;
57 int i1;
58 int i2;
59 bool b1 = false;
60 bool b2 = false;
61 if (x->getType() == CSPConstraint::VARIABLE | x->getType() ==
CSPConstraint::OPERATOR)
62 {
63 r1 = generateVariable(*x);
64 b1 = true;
65 }
66 else
67 if (x->getType() == CSPConstraint::INTEGER)
68 {
69 i1 = x->getInteger();
70 }
71
72 if (y->getType() == CSPConstraint::VARIABLE | y->getType() ==
CSPConstraint::OPERATOR)
73 {
74 r2 = generateVariable(*y);
75 b1 = true;
76 }
77 else
78 if (y->getType() == CSPConstraint::INTEGER)
79 {
80 i2 = y->getInteger();
81 }
82
83 Gecode::IntRelType ir;
84 switch(r)
85 {
86 case CSPConstraint::EQ:
87 ir = IRT_EQ;
88 break;
89 case CSPConstraint::NE:
90 ir = IRT_NQ;
91 break;
92 case CSPConstraint::LT:
93 ir = IRT_LE;
94 break;
95 case CSPConstraint::LE:
96 ir = IRT_LQ;
97 break;
98 case CSPConstraint::GE:
99 ir = IRT_GQ;
100 break;
101 case CSPConstraint::GT:
102 ir = IRT_GR;
103 break;
104 }
105
106 if (b1)
107 {
108 if (b2)
109 Gecode::rel(this, r1, ir, r2, b_[boolvar]);
110 else
111 Gecode::rel(this, r1, ir, i2, b_[boolvar]);
112 }
113 else
114 {
115 if (b2)
116 Gecode::rel(this, i1, ir, r2, b_[boolvar]);
117 else
118 Gecode::rel(this, i1, ir, i2, b_[boolvar]);
119
120 }
121 }
This is not very nice, but maybe i have to change my tree structure for
better code.
(as you can see i wanted to avoid all the different kind of variables of
type IntVar and integer and all the if else constructs)
But, with this code written i do get some errors, because the rel method
is not defined for constants
as:
- both arguments
- first argument
so i can not write
rel(this, 5, IRT_GR, x, b);
Why?
Do i have manually to flip the operands ?
Christian Schulte wrote:
> Yes, it is even worse: it sacrifices propagation!
>
> If you need to get started look to the code that posts propagators based on
> LinExpr and LinRel values. That is actually nothing but a tree analyzer
> posting the minimal number of required propagators for linear relations.
>
> Cheers
> Christian
>
> --
> Christian Schulte, www.ict.kth.se/~cschulte/
>
>
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Max
> Sent: Tuesday, October 28, 2008 1:56 PM
> To: Mikael Zayenz Lagerkvist
> Cc: users at gecode.org
> Subject: Re: [gecode-users] Generating constraints
>
> I have no problem in writing a tree analyzer but i looked for a uniform
> representation of the variables, operators, relations and constants, so
> i do not have to write an extra function for all of them.
> I want to write
>
> recursive_function_call rfc(X):
> IntVar temp;
> //switch for operator
> add(rfc(x1), ADD, rfc(x2), temp);
> return temp;
>
> I don't want to distinguish the leafs of the node at this step. So i
> need a uniform return value.
> PS: Does it influence the performance if i use temporary variables for
> my constants.
>
> IntVar x(this, 5,5);
>
>
>
>
> Mikael Zayenz Lagerkvist wrote:
>
>> Hi,
>>
>> If you have a tree representing an expression, then you should write a
>> tree-analyzer (a tree-walker for example) that posts constraints that
>> correspond to the tree. This is how the linear expressions in Gecodes
>> MiniModel works. For more information on writing tree analyzers, see a
>> compiler text as it corresponds to instruction selection.
>>
>> There is no way to undo a tell - you have to copy the space.
>>
>> Cheers,
>> Mikael
>>
>>
>> On Tue, Oct 28, 2008 at 12:58 PM, Max <chaosangel at gmx.de> wrote:
>>
>>
>>> Hello all,
>>>
>>> i currently try to post constraints and need your help.
>>> I have my constraints not in a textual format, but in a self made tree
>>> structure of the form
>>>
>>>
>>> rel">="
>>> / \
>>> op+ const=5
>>> / \
>>> var=x const=7
>>>
>>>
>>> (i hope this is readable)
>>>
>>> Now i want to generate and post a gecode constraint of it.
>>> Is there an easy way to recursivly define a constraint, because it seems
>>> to me that there is no baseclass or something that can be used.
>>>
>>> I wanted to to something of the form
>>>
>>> GeCodeConstraint recursive_converter(MyConstraint)
>>> {
>>> if "variable" return x;
>>> if "constant" return 5;
>>> if "op+" return recursive_converter(left_node) +
>>> recursive_converter(right_node);
>>> if "rel>=" return recursive_converter(left_node) >=
>>> recursive_converter(right_node);
>>> }
>>>
>>>
>>> I i found for GeCodeConstraint was MiniModel::LinRel<>, is there
>>> something more uniform, because i want to use boolean and integer
>>> variables (reified constraints) and stuff.
>>> (the arithmetic functions seem very generic returning a variable, but
>>> then a lot of extra variables would have to be generated)
>>>
>>>
>>> Any ideas ?
>>>
>>> 2nd question:
>>>
>>> Is there a way to post the value of a variable not in form of a
>>> constraint, so "branch" on a boolean variable but being able to undo it
>>>
> so
>
>>> so
>>> b[0].set(0);
>>> //after some time
>>> b[0].set(1);
>>>
>>> without copying the whole space?
>>>
>>> Thank you a lot.
>>>
>>> Max
>>>
>>> _______________________________________________
>>> 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
>
>
More information about the gecode-users
mailing list