Re: How to work List and Array together on QAP

Hi,

Earlier, I wrote a reply to Sirirat only, but after
reading Warwick Harvey's message I realised I should
have sent it to the list.
Below I attach approximately what I wrote; the gist
is that (what I call) array constraints are needed.

Cheers,
Sebastian

===================

|  After compiling, the error message is "instantiation fault in element(1, [_13534........", 

As Warwick said, the reason is that the element/3 constraint
expects a list of integers, while you're calling it with a list of
variables.  But this is no problem here since element/3 is not used as
a constraint: it just looks up the Ith and Kth element in the Layouts
list for constants I,K.
So one can reformulate this, or write a lookup procedure.

|              C #= F[I,K] * D[X,Y]

This one is more difficult.  While F[I,K] is again just a lookup with
constants I,K; the expression D[X,Y] is an access to the array D with
variables X and Y in the index.  It's a constraint on the three
variables X, Y, Dxy = D[X,Y].

Eclipse doesn't really have built-in support for such array constraints
(although lib(propia) is as usual an option), but I once wrote a
library for that very purpose, available at
	http://homepages.cwi.nl/~sbrand/Project/AC/array_constraints.pl
With it, and the rewritten version of your program that I attach, one
gets
	[eclipse 2]: main(4, Cost, Layouts).
	Found a solution with cost 517
	...
	Found a solution with cost 462

	Cost = 462
	Layouts = [1, 4, 3, 2]
	Yes (0.03s cpu)

===================

:- lib(fd).
:- lib(branch_and_bound).
:- lib(array_constraints).


main(N,Cost,Layouts):-
	length(Layouts, N),
	Layouts :: 1..N,
	alldifferent(Layouts),
	Y =.. [[] | Layouts],	%%  array Y = list Layouts
	D=[](	[] ( 0, 5, 7, 4),
		[] ( 8, 0, 5, 10),
		[] ( 4, 5, 0, 8),
		[] ( 2, 3, 7, 0)),
	F=[](	[] ( 0, 10, 7, 11),
		[] ( 8, 0, 5, 10),
		[] ( 5, 5, 0, 8),
		[] ( 9, 3, 7, 0)),

	(for(I, 1, 4), fromto(0, In1, Out2, Objective),
	param(D, F, Y)
	do
		(for(K, 1, 4), fromto(In1, In2, C+In2, Out2),
		param(D, F, Y, I)
		do
			%element(I,Layouts,X),
			%element(K,Layouts,Y),
			Yi is Y[I], Yk is Y[K], Fik is F[I,K],
			%% or also: { Yi = Y[I], Yk = Y[K], Fik = F[I,K] }
			{ Dyiyk = D[Yi,Yk] },  %%  array constraint!
			C #= Fik * Dyiyk
			%C #= F[I,K] * D[X,Y]
		)
	),
	Cost #= Objective,
	min_max(labeling(Layouts), Cost).