Re: Question

Hi Farouk,

Sorry for the slow reply --- too many things to do, not enough time to
do them.  :(


Some notes and comments on your program:

>         A1 ## 1, A2 ## 2, A3 ## 3, A4 ## 4, A5 ## 5, A6 ## 6, A7 #= 1,

I'm not sure what these `##' constraints are for.  Are they just extra
constraints for your problem that you haven't told me about?

>         suspend(sum(A1, A2, A3, A4, A5, A6, A7, C1, C2, C3, C4, C5, C6,
> C7,
>         D1, D2, D3, D4, D5, D6, D7), 3, [A1 -> inst]),

I very much doubt that this does what you're expecting it to do.  What
it does is waits until `A1' has its value fixed, and then calls
`sum/21'.  More on this later.

>         T1 #= 2,
>         (A1 #= 2) #=> (T2 #= T1 + D1),
>         (A1 #= 3) #=> (T3 #= T1 + D1),
>         (A1 #= 4) #=> (T4 #= T1 + D1),
>         (A1 #= 5) #=> (T5 #= T1 + D1),
>         (A1 #= 6) #=> (T6 #= T1 + D1),
>         (A1 #= 7) #=> (T7 #= T1 + D1),
> 
>         (A2 #= 3) #=> (T3 #= T1 + D1 + D2),
[etc.]

Yes, these constraints should work, but as you've noted, it's a pretty
ugly way of doing it.  One way of improving on the above is to introduce
a new set of variables, corresponding to the cost at the arc visited
first, second, third, etc.  I'll call these AC1, AC2, etc.  Then you
could have:

	AC1 = 2,
	AC2 #= AC1 + D1,
	AC3 #= AC2 + D2,
	etc.
and
	(A1 #= 2) #=> (T2 #= AC1),
	(A1 #= 3) #=> (T3 #= AC1),
	(A1 #= 4) #=> (T4 #= AC1),
	...

	(A2 #= 3) #=> (T3 #= AC2),
	etc.

This simplifies the constraints considerably, but still sets up a large
number of constraints.  A neater way of achieving something similar with
fewer constraints would be to put the `Ti's in a matrix and replace all
the `#=>' constraints with:

	suspend(subscript(TMatrix, [A1], AC1), 3, [A1->inst]),
	suspend(subscript(TMatrix, [A2], AC2), 3, [A2->inst]),
	suspend(subscript(TMatrix, [A3], AC3), 3, [A3->inst]),
	etc.

This simply binds `ACi' to the relevant `Tj' whenever `Ai' is bound (so
that we know which `Tj' to bind it to).

I think you then end up with about 2N fairly simple constraints rather
than N^2 increasingly complicated ones.  It's possible that you'll end
up with less propagation (e.g. if the system figures out that `T2'
cannot be equal to `AC1' before it knows what value `A1' takes), but I
don't think that will be the case here.  Besides, it's usually best to
start off with the simpler version, and only add the extra complexity if
you determine that you need the better propagation.

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

Since the `Tij' aren't referred to anywhere else, you could just put the
values directly into the matrix.  Also, if you're just assigning a value
to a variable, you don't have to use `#=' --- `=' works as well (i.e.
`T12 = 0', etc.).  Probably not a big deal either way (depends what you
like stylistically: I personally prefer to use `#=' only when there's
real constraint solving happening).

>         (nonvar(A1), nonvar(A2), nonvar(A3),
>         nonvar(A4), nonvar(A5), nonvar(A6), nonvar(A7) ->

This is where this `sum' predicate all goes wrong.  As noted above,
`sum' does not get called until `A1' has its value fixed.  Note that at
this point, it is unknown whether any of the other variables have been
fixed or not.  It turns out that `sum' actually gets called twice. 
During the call to `min_max', `A1' is assigned during labelling, then
this binding is undone (normally this would happen multiple times while
the optimal value is searched for, but in this case only once), and then
once the optimal cost is found, `A1' is assigned the value it had when
that optimal cost was found.

The first time `sum' is called, only `A1' and `A7' have values assigned,
which means the test fails, and so all the interesting subscripts, etc.
don't get called.  Without any `Vi's and `Di's being assigned values or
constrained in any meaningful way, it is impossible to work out anything
about `T8', and so the `min_max' procedure simply sets it to the
smallest finite domain value possible (-10000000).  Since `min_max'
knows it can't do any better than this, it stops at this point.

The second time `sum' is called is when `min_max' sets the variables to
the values they had when the optimal solution was found.  On this
occasion they all have their values fixed by the time `sum' actually
gets called, so all the subscript calls, etc. *are* executed this time,
so all the `Vi's and `Di's are given the correct values, and the correct
value for `T8' is obtained.

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

If all the `Ai's are ground when this is called, then yes, it'll do what
you want.  However, nothing will be known about the `Vi's until that
point, which means you'll get almost no benefit from your constraints
until you've fixed all your variables, which is very bad.  Better would
be to have each subscript only wait for the `Ai's it cares about, but
better is to have a two-dimensional version of the element constraint,
as discussed in my last email.



I'm still a bit concerned about the model being used here.  The
ambiguity that arises because an arc can be traversed more than once
worries me, particularly since you want to put constraints on the
cumulative cost at the point the arc is traversed.  With the way things
stand, all you can guarantee is that one of the traversals of a given
arc will satisfy the cumulative cost constraints you place on that arc
--- any other traversals of that arc will be free to violate those
constraints.  If that's exactly what you want, then fine, but it still
worries me.  :)  Perhaps if you can tell me what you're intending to
achieve by imposing constraints on the `Ti's, I can have a go at
formulating a different model which allows you to express the
constraints you want while avoiding the current ambiguities.

Of course, if anybody else out there has been following the discussion
and would like to contribute modelling ideas, you're welcome to jump
in.  :)



Finally for today, some comments on coding style.  Firstly,
indentation.  Normally the head of a clause is placed flush left, but
even if not, the body should be indented relative to the head.  Reading
your code, it is extremely difficult to see where one predicate ends and
the next one starts (initially, I didn't realise that there was more
than one predicate).  Also, whenever you have nested structures
(if-then-else `( -> ; )', disjunction `( ; )', do loops, etc.), the
contents should be indented so that it's clear what the scope of the
structures are.  My preferred layouts for these structures are like so:

	% If-then-else with a short (single line) condition.
	( ... ->
		...
	;
		...
	),

	% If-then-else with a long (multiple line) condition.
	(
		...
	->
		...
	;
		...
	),

	% Disjunction.
	(
		...
	;
		...
	),

	% Do loop.
	(
		...
	do
		...
	).

The amount of indenting you use is up to you, but I suggest 4 or 8
characters.

Secondly, it's usually a good idea to try to avoid hard-coding aspects
of the particular problem you're trying to solve, so that the program
works fine on different (and different-sized) problems.  Once you get in
the habit, this usually isn't too much trouble to do right from the
start.  With your current program, it would require a significant amount
of work to, say, add a new arc to your problem.  I know you're still
messing around with it trying to get it to work, but the more code you
write before you generalise it, the more work it is to make it general
when the time comes.

Note that if you don't like or are not comfortable with recursion in
ECLiPSe, there are a number of useful iterator constructs (do loops)
available.  See the section `ECLiPSe-specific Language Features' in the
user manual for details.  They may take a while to get used to (they
were completely alien to me when I first encountered them, probably
because I was too used to using recursion for loops is logic programming
languages), but they're quite handy once you've got the hang of them.


Anyway, that's more than enough from me for today.  :)

Cheers,
Warwick