# Re: Question

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>
```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