Re: Question

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)