[gecode-users] Generating constraints
Max
chaosangel at gmx.de
Tue Oct 28 14:53:52 CET 2008
I'm using Gecode as a library (of course :-) ) and don't know if the
performance will suffer using such an interface. I dont want to go back
to textual representation, as i would have to build it.
Searching your online documentation i found nothing using "Zinc" or
"minizinc" as search words. Only for FlatZinc i found an operation
writing flatzinc output, but i would need the input. Where can i find it.
Max
Christian Schulte wrote:
> Yes, you have to flip (or just normalize your tree before).
>
> Remember, Gecode is a library with a minimal interface: only variants that
> matter for efficiency are there. That explains that some variants are just
> not there. Maybe we should change that...
>
> On a different take. Did you consider translating your representation to
> MiniZinc and use the MiniZinc to FlatZinc converter and Gecode's flatzinc
> interface?
>
> 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 2:36 PM
> To: Christian Schulte
> Cc: 'Mikael Zayenz Lagerkvist'; users at gecode.org
> Subject: Re: [gecode-users] Generating constraints
>
> 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
>>
>>
>>
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>
More information about the gecode-users
mailing list