Non-contiguous and variable index sets of a two-dimensional array?

[Andrew Gill]

This is the essence of the problem. 

I have a two-dimensional square array S of integers that is generated from integer decision variables array[1..p,1..p] of var 1..k*k: S; (where p<k are integer parameters).

Suppose p=3 and k=7 and with particular values for my decision variables I have

S = [|2, 5, 10 |
    7, 12, 5 |
    12, 17, 22|];

I want to construct another two-dimensional array E where (mathematically at least) E[S[i,j],S[j,i]]=1. For example E[5,7]=1 when i=1 and j=2.

Currently I use: 

array[1..k*k,1..k*k] of var 0..1: E; 

constraint([E[S[i,j],S[j,i]]=1 | i,j in 1..p where i<j]);

But this seems fairly wasteful, since there are at most p*p unique values in S, so I would like to do something like, but this doesn't work: 

var set of 1..p*p: svals; 

constraint svals={S[i,j] | i,j in 1..p};

array[svals,svals] of var 0..1: E; 

constraint([E[S[i,j],S[j,i]]=1 | i,j in 1..k where i<j]);

I thought perhaps I could use something like, but again it doesn't work: 

array[1..p*p,1..p*p] of var 0..1: E; 

and then using a mapping of the sorted unique values in S to their position with:

constraint([E[arg_val(svals,S[i,j]),arg_val(svals,S[j,i])]=1 | i,j in 1..k where i<j]);

 So I was hoping to get some advice on Non-contiguous and variable index sets of a two-dimensional array.

Thanks :-)

Andrew

[Jip Dekker]

Hi Andrew,

It seemed I had missed this email when it initially arrived. There are some ways to deal with non-continuous index sets. The most straight-forward is to create a new enumerated type that hides the non-continuous nature (letting it be handled in the constructor):

enum SVals = Idx({S[i,j] | i,j in 1..p});
array[SVals, SVals] of var 0..1: E;
constraint forall(i,j in 1..p where i<j)(
  E[Idx(S[i,j]),Idx(S[j,i])] = 1
);

However, this only works if `S` is a known matrix. If, as you describe, it contains decision variables, then it gets a little more complex. In general, it will depend on what other constraints “E” is involved in.

A possible way forward might be to keep only the indexes of the `=1` parts of the matrix:

array[1..p*p] of var tuple(int, int): E ::output = [
  (S[i,j], S[j,i]) | i, j in 1..p
];

Cheers,

Jip