From: FAROUK AMINU <f.aminu_at_lancaster.ac.uk>

Date: Tue 24 Oct 2000 06:40:11 PM GMT

Message-ID: <Pine.GSO.4.21.0010241900290.11871-100000@unixa.lancs.ac.uk>

Date: Tue 24 Oct 2000 06:40:11 PM GMT

Message-ID: <Pine.GSO.4.21.0010241900290.11871-100000@unixa.lancs.ac.uk>

Dear Warwick, Actually after reading your mail again just now I realised I have not answered the questions you rased and I qoute:- Some questions for you. Do you need all of C1, C2 & C3, or are you just > interested in the overall total cost? Do you specifically need the > accumulated costs at node 1, 2 & 3, or will the costs after the first, > second and third nodes do (and you can figure out which nodes these are > later)? Similarly, do you need V1, V2 & V3 to indicate which are the > first, second, and third nodes (respectively), or could you instead have > variables (say) O1, O2 & O3 which give the position in the sequence for > nodes 1, 2 & 3, respectively? (I've used this in the above solution. > E.g. corresponding to your V1 = 3, V2 = 1, V3 = 2 example, you would > have O1 = 2, O2 = 3, O3 = 1, saying that node 1 is the second node to be > visited, node 2 is the third node, and node 3 is the first.) I thus decided to post exactly what I did. My program is as below:- :-lib(fd). solve(Arcs, Time):- %this sets the variables for the arcs(edges) to visit. Arcs = [A1, A2, A3, A4, A5, A6, A8], Arcs::1..7, alldifferent(Arcs), %Ti is the time at which arc i is traversed. Time = [T1, T2, T3, T4, T5, T6, T7, T8], %asumes that arc 1 is the starting arc and the last arc, thus not %present here except constraining A7 to be the last arc. A1 ## 1, A2 ## 2, A3 ## 3, A4 ## 4, A5 ## 5, A6 ## 6, A7 #= 1, %if Ai is given a value j, then Ci becomes the cost of traversing that %arc j. element(A1, [2, 3, 5, 5, 1, 2, 5], C1), element(A2, [2, 3, 5, 5, 1, 2, 5], C2), element(A3, [2, 3, 5, 5, 1, 2, 5], C3), element(A4, [2, 3, 5, 5, 1, 2, 5], C4), element(A5, [2, 3, 5, 5, 1, 2, 5], C5), element(A6, [2, 3, 5, 5, 1, 2, 5], C6), element(A7, [2, 3, 5, 5, 1, 2, 5], C7), suspend(sum(A1, A2, A3, A4, A5, A6, A7, C1, C2, C3, C4, C5, C6, C7, T1, T2, T3, T4, T5, T6, T7, T8), 3, [A1 -> inst]), %initially, the model was just a labeling model but min_max was used %to optimise the final acumulated value. min_max(labeling(Arcs), T8). sum(A1, A2, A3, A4, A5, A6, A7, C1, C2, C3, C4, C5, C6, C7, T1, T2, T3, T4, T5, T6, T7, T8):- %the Tijs are the shortest times to go from the end of node i to the % begining of node j. 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 was used to select the Tijs depending on the values of the %Ais. 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)), (nonvar(A1), nonvar(A2), nonvar(A3), nonvar(A4), nonvar(A5), nonvar(A6), nonvar(A7) -> 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), %my biggest problem is here. I was lucky after minimising the value of %T8, I have the following results: %Arcs = [2, 3, 4, 5, 6, 7, 1] %Time = [3, 5, 5, 6, 2, 9, 2, 32] %Yes (0.00s cpu) %Thus I realised I can just add the values of the Tis straight to get %the values I need. That is, T1 is const. because it is the starting %arc (edge), then because the ordering is 2,3,4,5,6,7,1, I can easily %add the Tis as below. But suppose the sequencing is 2,3,4,6,7,5,1; then %I need T6 #= T4 + C4 + V4, T7 #= T6 + C5 + V5, T5 #= T7 + C6 + V6, %T8 #= T5 + C7 + V7 - 2. T1 #= 2, T2 #= T1 + C1 + V1, T3 #= T2 + C2 + V2, T4 #= T3 + C3 + V3, T5 #= T4 + C4 + V4, T6 #= T5 + C5 + V5, T7 #= T6+ C6 + V6, T8 #= T7+ C7 + V7 - 2; true). The result from runing the above model is:- Arcs = [2, 3, 4, 5, 6, 7, 1] Time = [2, 5, 10, 15, 21, 23, 32, 32] Yes (0.01s cpu). The above ordering of the Tis can be done using the if-then-else, but in large problems like having between 10 to 50 nodes I think the using if-then-else statement will entail having about N! constraints. This is my weakness and which I am trying to clarify and avoid. Please Kindly help me out of this problem. My second issue is that this model is giving me the value: Found a solution with cost -10000000, but giving correct value in the list. Thanking you all for your help and care. with reagrds to you all, Farouk =============================================================================== UMARU FAROUK AMINU DEPARTMENT OF MANAGEMENT SCIENCE LANCASTER UNIVERSITY LANCASTER LA1 4YX U.K. +44 (0)1524 593865 (School) +44 (0)1524 383619 (Home) +44 (0)1524 844885 (Fax)Received on Tue Oct 24 19:41:36 2000

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