2.2 Yes, for expr() it works. There is normally no benefit in adding more variables to branching. In certain cases it can be beneficial if the variables are interesting for a branching heuristic.
3. Yes exactly, as constraint propagation is incomplete you always have to branch until all variables are assigned. Otherwise you do not know in general that you have reached a solution. Christian -- Christian Schulte, www.ict.kth.se/~cschulte/ -----Original Message----- From: Max Ostrowski [mailto:[email protected]] Sent: Tuesday, June 14, 2011 3:50 PM To: [email protected]; [email protected] Subject: Re: RE: [gecode-users] Branching on temporary variables Thank you for your quick response. Just to clarify for me 2.2, if i only use expr(), and the resulting variables in global constraints, then i do not need to branch on any temporary variables to be "complete". Right? If so, does it give me any improvements? for example: IntVarArray temp(2); temp[0] = expr(a+b); temp[1] = expr(c+d); distinct(temp2). If i now branch on {a,b,c,d} i will find all solutions. But i could also branch on {a,b,c,d,temp[0],temp[1]} to find all solutions. Can this be considered "better" in terms of possible complexity, or is there any "experience" from your side that you would recommend to branch on as much or few variables as possible? (while still enumerating all models) 3: I tried my little experiment now (sorry, i just was too lazy before) a*b==0 where a\in{0..2} and b\in{0..2} and i do branch on {a} only. So i will only get 3 (partial) Solutions: Answer: 1 a=0 b=[0..2] Answer: 2 a=1 b=0 Answer: 3 a=2 b=0 So i projected on {a}. But as i now see, i can not be sure if these (partial) solutions can be extended to a complete solution, right ? (maybe there is no complete solution a=0, i will not know yet) Best, Max -------- Original-Nachricht -------- > Datum: Tue, 14 Jun 2011 15:12:48 +0200 > Von: "Christian Schulte" <[email protected]> > An: "\'Max Ostrowski\'" <[email protected]>, [email protected] > Betreff: RE: [gecode-users] Branching on temporary variables > Hi, > > 1) Not quite. Instead of var1.post(...) use expr(home, var1) (that is, the > documented interface not its implementation) > > 2) > 2.1) In principle, of course! However, for all expressions available > through > expr() you can be sure that the resulting variables are assigned if all > variables in the expressions are assigned. > 2.2) As said, you have to in general. > > 3) Do not understand the question but you get 6 solutions as there are six > solutions! > > Christian > > -- > Christian Schulte, www.ict.kth.se/~cschulte/ > > > -----Original Message----- > From: [email protected] [mailto:[email protected]] On Behalf > Of Max Ostrowski > Sent: Tuesday, June 14, 2011 10:37 AM > To: [email protected] > Subject: [gecode-users] Branching on temporary variables > > Hello everybody, > > i have some expressions (linear and non-linear) stored in a > "Gecode::LinExpr" object. > > Know i want to post a global constraint on them. > > So, expressions for example: > //pseudocode > LinExpr var1 = a+b*c; > LinExpr var2 = 4-7 > > and i want the results of them to be allDifferent (distinct) > > IntVarArray z(home,2); > z[0] = var1.post(home); > z[1] = var2.post(home); > > distinct(home,z); > > > 1: Is this the right way to do this? > 2: I do branching on the variables a,b,c. > 2.1: Can it happen that some of the temporary variables z[i] stay > unassigned (regarding any linear or non-linear expression)? > 2.2: Does it make an advantage to branch on {a,b,c,z[1..n]} instead of > {a,b,c} ? Can this decrease complexity, as it is the case with > conjunctions > in SAT. > > 3: If i post the constraint a*b==0 a\in{0..2} and b\in{0..2} and i do > branch > on {a}, do i get 3 or 6 solutions. (So, are my solutions really projected > on the branching variables?) > > > Thanks a lot in advance, > > 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 > -- Empfehlen Sie GMX DSL Ihren Freunden und Bekannten und wir belohnen Sie mit bis zu 50,- Euro! https://freundschaftswerbung.gmx.de _______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
