Re: Question

Dear Warwick,

The problem is that of finding an Euler tour in a graph. Let's take the
directed version for the moment. I have five nodes and seven links (Arcs),
I have formulated the problem of determining the Euler tour and that of
determining the shortest path in the graph. My main concern at the moment
is to fromulate the problem to find exactly at which time each arc is
traversed. The graph has two junctions (from node 3 to 4 or 3 to
5 and from node 5 to 2 or 5 to 1). I decided to number the arcs as arc1 to
arc7. My reason for doing it this way is to generalise the model so as to
accomodate all situations. Looking at the graph one can pick the arcs by
eye and thus say that T1 is the time to traverse arc1 and T2 for
arc2,.., T7 for arc7. arc1 is the starting arc and the finishing arc. One
can write the total accumulated time as Tot #= t1 + t2 + t3 + t4 + t5 + t6
+ t7, if the best way to traverse the arcs is starting with arc1 then arc2
up to arc7 in this sequence. It is evident that this would not work on
computer as a general model.

I thus decided to write the program in such a way that after traversing
the first arc it is left to the optimisation function to chose which arc 
to traverse next, this will automatically set the directed sequence and
decide at the junctions, which way to go. I made a pre-processing of the
shortest times between the arcs, thus my Tij's are the times between
the end of arc1 to the begining of arcj. Thus to go to arcj from arci, the
time Tj should be Ti + Tij + tj. Thus T2 #= T1 + T12 + t2 if arc2 id
traversed after arc1 and so on.

>From my formulation, I used the element constraint to set the ti's, thus
if A1 #= 2, then the value t2 will be assigned to C1, this is clear from
the code:

	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),

The links in my graph are([1,2],[2,3],[3,4/3,5],[4,1],[5,2/5,1] with times
2,3,5/1,5,2/5).
Links [1,2 = arc1], [2,3 = arc2], [3,4 = arc3], [4,1 = arc4], [3,5 =arc5],
[5,2 =arc6], [5,1 = arc7].

The Tij's are added knowing that in determining an Euler tour an arc must
be traversed exactly once (but after balancing some of the arcs are going
to be duplicated which means you can traverse an arc at least once). I
used the matrix to select the Tij's based on which arc is traversed after
which and assigned the values to the Vi's. Thus, if arc2 is traversed
after arc1 then, the subscript should be [row1,col2] which will pick T12,
if arc7 is traversed after arc2, then the subscript is [row2,col7], which
will pick T27 and so on. The sequence will thus be 2,7,...,1. I have
constrained A7 to take value 1 so that arc1 is the final arc to traverse,
the issue now is left to the solver to select from which arc to go back to
arc1 (due to optimisation). There is no harm to this as the shortest paths
solutions have taken care of coming back to arc1 through either arc7 or
arc4 and is captured in the Tij's.

It can be understood that if I have sequence like: 2,3,4,5,6,7,1 this
means that I will go to arc2 from arc1, arc3 from arc2, arc4 from 3, 5
from 4, 6 from 5, 7 from 6 and 1 from 7. I used T8 to take care of the
time to get back to arc1, but since the general formular takes into
account the times to come from arci to arcj and the time to service arcj
then I subtracted the time to service arc1 from the total because it is
going to be counted twice. You can see in my code that I used T1 #= 2,
then I continued accumulating the values of the Ti's. Now because of my
sequence, I can write T2 #= T1 + V1 (which is T12 in this case) + C1
(which is the time to traverse arc2), 

T3 #= T2 + V2 (which is T23 in this case) + C2 (which is the time to
traverse arc3), ...., T8 #= T7 + V7(which is T71 in this case) + C1( which
is the time to service arc1) - 2 (which is the time to service arc1).

This does what I want but you can see that it is not general. My aim is to
constrain the Ti's to go with the values of the Ai's as in the above case.
That is if the sequence is 4,5,6,1,3,7,2, the sequece for the Ti's should
be T4,T5,T6,T1,T3,T7,T2. You can see that from my formulation the Ci's and
the Vi's will not change, that is,

T1 #= 2,
T4 #= T1 + V1 (which is T14) + C1 (which is t4),
T5 #= T4 + V2 (which is T45) + C2 (which is t5),
T6 #= T5 + V3 (which is T56) + C3 (which is t6),
T1 #= T6 + V4 (T61) + C4 (t1),
T3 #= T1 + V5 (T13) + C5 (t3),
T7 #= T3 + V6 (T37) + C6 (t7),
T2 #= T7 + V7 (T72) + C7 (t2),
T8 #= T2 - 2 (t1),

You can make the above using if then else constraint, that is, if 
A1=2,A2 =3,A3=4,A4=5,A5=6,A6=7,A7=1, =>
T1=2,T2=T1+(COST1),T3=T2+COST2,...;
A1=3,A2=4,A3=5,A4=6,A5=7,A6=2,A7=1 =>
T1 =2,T3=T1+COST1,T4=T3+COST2,...,T2=T7+COST6,T1=T2+COST7,

and so on. But then this will be dependent on the number of arcs available
and if the number is too large then it is going to be impossible to write
all the constraints. My weakness is my inability to match the Ti's with
values assigned to the Ai's during optimisation of the total time.

Your earlier formulation constrain C1 to go with A1, C2 with A2 and C3
with A3, but my problem is to constrain T1 to go with value 1 it does not
matter which of the Ai's is given that value. Thus T2 goes with value 2,
T3 goes with value 3 and so on. Finally, T8 sums up the whole times and is
then optimised.

I am really grateful for your interest in this problem and hope this
information sheds more light to the problem. 

Thanking you,

with best regards,

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)