# Re: Question

From: FAROUK AMINU <f.aminu_at_lancaster.ac.uk>
Date: Mon 27 Nov 2000 05:44:28 PM GMT
Message-ID: <Pine.GSO.4.21.0011271723550.15072-100000@unixc.lancs.ac.uk>
```Dear Warwick,

I realised that other users have not received my recent mail on the
subject and hence decided to send this one again. I have made
midifications to the problem after sending it to you. I now realised I can
use just one predicate for the whole program, I don't know if it is
better, but still I have been able to solve the problem in less time that
using the earlier formulation. I present the new program here:-

:-lib(fd).

solve(Arcs, Time):-

Arcs = [A1, A2, A3, A4, A5, A6, A7, A8],
Arcs::1..8,
alldifferent(Arcs),

A8 = 1,

element(A1, [0, 2, 3, 5, 5, 1, 2, 5], C1),
element(A2, [0, 2, 3, 5, 5, 1, 2, 5], C2),
element(A3, [0, 2, 3, 5, 5, 1, 2, 5], C3),
element(A4, [0, 2, 3, 5, 5, 1, 2, 5], C4),
element(A5, [0, 2, 3, 5, 5, 1, 2, 5], C5),
element(A6, [0, 2, 3, 5, 5, 1, 2, 5], C6),
element(A7, [0, 2, 3, 5, 5, 1, 2, 5], C7),
element(A8, [0, 2, 3, 5, 5, 1, 2, 5], C8),

Time = [T1, T2, T3, T4, T5, T6, T7, T8, Tot],

Matrix = m(r(0,0,2,5,10,5,6,6),
r(9,9,0,3,8,3,4,4),
r(6,6,3,0,5,0,1,1),
r(5,5,7,10,0,13,11,11),
r(0,0,2,5,10,5,6,6),
r(5,5,2,5,10,5,0,0),
r(9,9,0,3,8,3,4,4),
r(0,0,2,5,10,5,6,6)),

suspend(subscript(Matrix, [1,A1], V1), 3, [A1 -> inst]),
suspend(subscript(Matrix, [A1,A2], V2), 3, [A2 -> inst]),
suspend(subscript(Matrix, [A2,A3], V3), 3, [A3 -> inst]),
suspend(subscript(Matrix, [A3,A4], V4), 3, [A4 -> inst]),
suspend(subscript(Matrix, [A4,A5], V5), 3, [A5 -> inst]),
suspend(subscript(Matrix, [A5,A6], V6), 3, [A6 -> inst]),
suspend(subscript(Matrix, [A6,A7], V7), 3, [A7 -> inst]),
suspend(subscript(Matrix, [A7,A8], V8), 3, [A7 -> inst]),

(nonvar(A1) -> subscript(Matrix, [1,A1], V1); true),
(nonvar(A2) -> subscript(Matrix, [A1,A2], V2); true),
(nonvar(A3) -> subscript(Matrix, [A2,A3], V3); true),
(nonvar(A4) -> subscript(Matrix, [A3,A4], V4); true),
(nonvar(A5) -> subscript(Matrix, [A4,A5], V5); true),
(nonvar(A6) -> subscript(Matrix, [A5,A6], V6); true),
(nonvar(A7) -> subscript(Matrix, [A6,A7], V7); true),
(nonvar(A7) -> subscript(Matrix, [A7,A8], V8); true),

TMatrix = r(Tot, T2, T3, T4, T5, T6, T7, T8),

D1 #= V1 + C1,
D2 #= V2 + C2,
D3 #= V3 + C3,
D4 #= V4 + C4,
D5 #= V5 + C5,
D6 #= V6 + C6,
D7 #= V7 + C7,
D8 #= V8 + C8,

T1 #= 0,
PR1 #= T1 + D1,
PR2 #= PR1 + D2,
PR3 #= PR2 + D3,
PR4 #= PR3 + D4,
PR5 #= PR4 + D5,
PR6 #= PR5 + D6,
PR7 #= PR6 + D7,
PR8 #= PR7 + D8,

suspend(subscript(TMatrix, [A1], PR1), 3, [A1 -> inst]),
suspend(subscript(TMatrix, [A2], PR2), 3, [A2 -> inst]),
suspend(subscript(TMatrix, [A3], PR3), 3, [A3 -> inst]),
suspend(subscript(TMatrix, [A4], PR4), 3, [A4 -> inst]),
suspend(subscript(TMatrix, [A5], PR5), 3, [A5 -> inst]),
suspend(subscript(TMatrix, [A6], PR6), 3, [A6 -> inst]),
suspend(subscript(TMatrix, [A7], PR7), 3, [A7 -> inst]),

(nonvar(A1) -> subscript(TMatrix, [A1], PR1); true),
(nonvar(A2) -> subscript(TMatrix, [A2], PR2); true),
(nonvar(A3) -> subscript(TMatrix, [A3], PR3); true),
(nonvar(A4) -> subscript(TMatrix, [A4], PR4); true),
(nonvar(A5) -> subscript(TMatrix, [A5], PR5); true),
(nonvar(A6) -> subscript(TMatrix, [A6], PR6); true),
(nonvar(A7) -> subscript(TMatrix, [A7], PR7); true),
subscript(TMatrix, [A8], PR8),

min_max(labeling(Arcs), Tot).

This program gave the following results and it is doing what I wanted.
Arcs = [2, 3, 4, 5, 6, 7, 8, 1]
Time = [0, 2, 5, 10, 15, 21, 23, 32, 32]
Yes (2.65s cpu)

Found a solution with cost 32.

I hope yopu would not mind runing the program to have a feel of how it
works. My only problem at the moment is just what I mentioned in my other
mail which is not available in the archive. This formulation seems to work
alright but not on much bigger problems. I have tried solving a case with
19 arcs which I attached to you in my last mail but for some reasons the
solver gives the following message in the error and messages window:-

Found a solution with cost 320.

This result came in a fraction of a second.
However, it took up to 24 working hrs yet the solver could not prove
optimality. It remained working without being able to give any output in
the results window. This shows that there might be some uncountable
alternatives or just it is the way I formulated the problem. I have tried
my possible best to improve the problem by using different definitions to
the labeling predicate, yet nothing comes up.

I would very much appreciate your comments on how I could improve the
formulation given my problem with bigger problem.

Thanking you,

with 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)
```
Received on Mon Nov 27 17:44:54 2000

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