From: Warwick Harvey <wh_at_icparc.ic.ac.uk>

Date: Wed 01 Nov 2000 07:15:06 PM GMT

Message-ID: <3A006BBA.9BD1C6F1@icparc.ic.ac.uk>

Date: Wed 01 Nov 2000 07:15:06 PM GMT

Message-ID: <3A006BBA.9BD1C6F1@icparc.ic.ac.uk>

Hi Farouk, Sorry for the slow reply --- too many things to do, not enough time to do them. :( Some notes and comments on your program: > A1 ## 1, A2 ## 2, A3 ## 3, A4 ## 4, A5 ## 5, A6 ## 6, A7 #= 1, I'm not sure what these `##' constraints are for. Are they just extra constraints for your problem that you haven't told me about? > suspend(sum(A1, A2, A3, A4, A5, A6, A7, C1, C2, C3, C4, C5, C6, > C7, > D1, D2, D3, D4, D5, D6, D7), 3, [A1 -> inst]), I very much doubt that this does what you're expecting it to do. What it does is waits until `A1' has its value fixed, and then calls `sum/21'. More on this later. > T1 #= 2, > (A1 #= 2) #=> (T2 #= T1 + D1), > (A1 #= 3) #=> (T3 #= T1 + D1), > (A1 #= 4) #=> (T4 #= T1 + D1), > (A1 #= 5) #=> (T5 #= T1 + D1), > (A1 #= 6) #=> (T6 #= T1 + D1), > (A1 #= 7) #=> (T7 #= T1 + D1), > > (A2 #= 3) #=> (T3 #= T1 + D1 + D2), [etc.] Yes, these constraints should work, but as you've noted, it's a pretty ugly way of doing it. One way of improving on the above is to introduce a new set of variables, corresponding to the cost at the arc visited first, second, third, etc. I'll call these AC1, AC2, etc. Then you could have: AC1 = 2, AC2 #= AC1 + D1, AC3 #= AC2 + D2, etc. and (A1 #= 2) #=> (T2 #= AC1), (A1 #= 3) #=> (T3 #= AC1), (A1 #= 4) #=> (T4 #= AC1), ... (A2 #= 3) #=> (T3 #= AC2), etc. This simplifies the constraints considerably, but still sets up a large number of constraints. A neater way of achieving something similar with fewer constraints would be to put the `Ti's in a matrix and replace all the `#=>' constraints with: suspend(subscript(TMatrix, [A1], AC1), 3, [A1->inst]), suspend(subscript(TMatrix, [A2], AC2), 3, [A2->inst]), suspend(subscript(TMatrix, [A3], AC3), 3, [A3->inst]), etc. This simply binds `ACi' to the relevant `Tj' whenever `Ai' is bound (so that we know which `Tj' to bind it to). I think you then end up with about 2N fairly simple constraints rather than N^2 increasingly complicated ones. It's possible that you'll end up with less propagation (e.g. if the system figures out that `T2' cannot be equal to `AC1' before it knows what value `A1' takes), but I don't think that will be the case here. Besides, it's usually best to start off with the simpler version, and only add the extra complexity if you determine that you need the better propagation. > T12 #= 0, T13 #= 3, T14 #= 8, T15 #= 3, T16 #= 4, T17 #= 4, > > T21 #= 10, T23 #= 0, T24 #= 5, T25 #= 0, T26 #= 1, T27 #= 1, > > T31 #= 5, T32 #= 7, T34 #= 0, T35 #= 13, T36 #= 11, T37 #= 11, > > T41 #= 0, T42 #= 2, T43 #= 5, T45 #= 5, T46 #= 6, T47 #= 6, > > T51 #= 5, T52 #= 2, T53 #= 5, T54 #= 10, T56 #= 0, T57 #= 0, > > T61 #= 9, T62 #= 0, T63 #= 3, T64 #= 8, T65 #= 3, T67 #= 4, > > T71 #= 0, T72 #= 2, T73 #= 5, T74 #= 10, T75 #= 5, T76 #= 6, > > Matrix = m(r(0,T12,T13,T14,T15,T16,T17), > r(T21,0,T23,T24,T25,T26,T27), > r(T31,T32,0,T34,T35,T36,T37), > r(T41,T42,T43,0,T45,T46,T47), > r(T51,T52,T53,T54,0,T56,T57), > r(T61,T62,T63,T64,T65,0,T67), > r(T71,T72,T73,T74,T75,T76,0)), Since the `Tij' aren't referred to anywhere else, you could just put the values directly into the matrix. Also, if you're just assigning a value to a variable, you don't have to use `#=' --- `=' works as well (i.e. `T12 = 0', etc.). Probably not a big deal either way (depends what you like stylistically: I personally prefer to use `#=' only when there's real constraint solving happening). > (nonvar(A1), nonvar(A2), nonvar(A3), > nonvar(A4), nonvar(A5), nonvar(A6), nonvar(A7) -> This is where this `sum' predicate all goes wrong. As noted above, `sum' does not get called until `A1' has its value fixed. Note that at this point, it is unknown whether any of the other variables have been fixed or not. It turns out that `sum' actually gets called twice. During the call to `min_max', `A1' is assigned during labelling, then this binding is undone (normally this would happen multiple times while the optimal value is searched for, but in this case only once), and then once the optimal cost is found, `A1' is assigned the value it had when that optimal cost was found. The first time `sum' is called, only `A1' and `A7' have values assigned, which means the test fails, and so all the interesting subscripts, etc. don't get called. Without any `Vi's and `Di's being assigned values or constrained in any meaningful way, it is impossible to work out anything about `T8', and so the `min_max' procedure simply sets it to the smallest finite domain value possible (-10000000). Since `min_max' knows it can't do any better than this, it stops at this point. The second time `sum' is called is when `min_max' sets the variables to the values they had when the optimal solution was found. On this occasion they all have their values fixed by the time `sum' actually gets called, so all the subscript calls, etc. *are* executed this time, so all the `Vi's and `Di's are given the correct values, and the correct value for `T8' is obtained. > subscript(Matrix, [1,A1], V1), > subscript(Matrix, [A1,A2], V2), > subscript(Matrix, [A2,A3], V3), > subscript(Matrix, [A3,A4], V4), > subscript(Matrix, [A4,A5], V5), > subscript(Matrix, [A5,A6], V6), > subscript(Matrix, [A6,A7], V7), If all the `Ai's are ground when this is called, then yes, it'll do what you want. However, nothing will be known about the `Vi's until that point, which means you'll get almost no benefit from your constraints until you've fixed all your variables, which is very bad. Better would be to have each subscript only wait for the `Ai's it cares about, but better is to have a two-dimensional version of the element constraint, as discussed in my last email. I'm still a bit concerned about the model being used here. The ambiguity that arises because an arc can be traversed more than once worries me, particularly since you want to put constraints on the cumulative cost at the point the arc is traversed. With the way things stand, all you can guarantee is that one of the traversals of a given arc will satisfy the cumulative cost constraints you place on that arc --- any other traversals of that arc will be free to violate those constraints. If that's exactly what you want, then fine, but it still worries me. :) Perhaps if you can tell me what you're intending to achieve by imposing constraints on the `Ti's, I can have a go at formulating a different model which allows you to express the constraints you want while avoiding the current ambiguities. Of course, if anybody else out there has been following the discussion and would like to contribute modelling ideas, you're welcome to jump in. :) Finally for today, some comments on coding style. Firstly, indentation. Normally the head of a clause is placed flush left, but even if not, the body should be indented relative to the head. Reading your code, it is extremely difficult to see where one predicate ends and the next one starts (initially, I didn't realise that there was more than one predicate). Also, whenever you have nested structures (if-then-else `( -> ; )', disjunction `( ; )', do loops, etc.), the contents should be indented so that it's clear what the scope of the structures are. My preferred layouts for these structures are like so: % If-then-else with a short (single line) condition. ( ... -> ... ; ... ), % If-then-else with a long (multiple line) condition. ( ... -> ... ; ... ), % Disjunction. ( ... ; ... ), % Do loop. ( ... do ... ). The amount of indenting you use is up to you, but I suggest 4 or 8 characters. Secondly, it's usually a good idea to try to avoid hard-coding aspects of the particular problem you're trying to solve, so that the program works fine on different (and different-sized) problems. Once you get in the habit, this usually isn't too much trouble to do right from the start. With your current program, it would require a significant amount of work to, say, add a new arc to your problem. I know you're still messing around with it trying to get it to work, but the more code you write before you generalise it, the more work it is to make it general when the time comes. Note that if you don't like or are not comfortable with recursion in ECLiPSe, there are a number of useful iterator constructs (do loops) available. See the section `ECLiPSe-specific Language Features' in the user manual for details. They may take a while to get used to (they were completely alien to me when I first encountered them, probably because I was too used to using recursion for loops is logic programming languages), but they're quite handy once you've got the hang of them. Anyway, that's more than enough from me for today. :) Cheers, WarwickReceived on Wed Nov 01 19:16:25 2000

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:06 PM GMT GMT
*