3-dimensional data structure and storage efficiency

[Peter Greistorfer]

Another nice evening!

In a run-file, I'd like to maintain, change and access a data structure, built with params, which generally could be described as a vector[k=1..10] of matrices [i=1..5, j=1..7] (to give some exemplifying ranges). Naturally, that could be done by a 3-dimensional structure[1..10,1..5,1..7], but the question is if this is the most effective way regarding storage requirement? (Ideally, depending on k, the matrix-sizes could dynamically vary ...)

Feeling grateful for any hint, best regards,

Peter

[AMPL Google Group]

If your matrix is a dense matrix, then you could represent it by using 3-dimensional structure. I am assuming that 3-dimensional structure is the param declaration of the matrix as described in https://ampl.com/BOOK/CHAPTERS/12-data.pdf (pp: 148). However, if you have sparse matrix, then you could store non-zero values and corresponding rows and columns. The non-zero representation will substantially reduce the memory requirement.

Thanks
Paras

--
Paras Tiwari
am...@googlegroups.com

{#HS:567993197-6048#}

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Peter Greistorfer]

Hm ..., not exactly pp.148, which - sorry - confuse me a little bit, because they focus on the LINK-theme. My view is typically index-oriented, where elements of the 3-dimensional structure (like the 12 elements of an C-array A[2][2][3]) can be directly accessed by numerical triples of indices, which includes for-manipulation. (And yes, I know, both views, in the end, are more or less identical.)

Regarding density. Yes all is dense, but not constantly sized, since the K matrices actually vary in their dimensions I x J (where the perfect C-analogy would be a dynamic pointer-based construction for i=1,...,I and j=1,...,J, while K can be perfectly estimated in advance).

[AMPL Google Group]

You can use following construct to declare your array:

param K;
param I {1..K};
param J {1..K};

param array {k in 1..K, i in 1..I[k], j in 1..J[k]};

--
Paras Tiwari
am...@googlegroups.com

{#HS:567993197-6048#}

On Wed, Apr 25, 2018 at 6:17 AM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Hm ..., not exactly pp.148, which - sorry - confuse me a little bit, because they focus on the LINK-theme. My view is typically index-oriented, where elements of the 3-dimensional structure (like the 12 elements of an C-array A[2][2][3]) can be directly accessed by numerical triples of indices, which includes for-manipulation. (And yes, I know, both views, in the end, are more or less identical.)

Regarding density. Yes all is dense, but not constantly sized, since the K matrices actually vary in their dimensions I x J (where the perfect C-analogy would be a dynamic pointer-based construction for i=1,...,I and j=1,...,J, while K can be perfectly estimated in advance).

On Tue, Apr 24, 2018 at 8:31 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

If your matrix is a dense matrix, then you could represent it by using 3-dimensional structure. I am assuming that 3-dimensional structure is the param declaration of the matrix as described in https://ampl.com/BOOK/CHAPTERS/12-data.pdf (pp: 148). However, if you have sparse matrix, then you could store non-zero values and corresponding rows and columns. The non-zero representation will substantially reduce the memory requirement.

Thanks
Paras

--
Paras Tiwari
am...@googlegroups.com

[Peter Greistorfer]

... and I[k] as well as J[k] can be dynamically set at run-time, with different values over k?

[Peter Greistorfer]

More efficiently, I tried it right now on my own - and it works like a charm (you my check my lines below). The only question, which remains, is: if I span a 3-dimensional space by defining (and possibly modifying) K, I and J, and then define, say, 4 numbers within that space, does that mean a storage use of only 4 numbers or have I "wasted" the overall space of K*I*J numbers (where I know that "space of a number" is somewhat fuzzy ...)?

#==========================================================
reset;

param K;
param I {1..K};
param J {1..K};

param t{k in 1..K, i in 1..I[k], j in 1..J[k]};

printf "\n--- initial def: ----------------------------\n";
let K    :=  5;        # initial def
let I[2] :=  7;        # initial def
let J[2] :=  4;        # initial def
let t[2,6,4] := 264;

display K, I, J, t[2,6,4];

printf "--- increasin k within K: ---------------------\n";
let I[3] :=  7;        # increasing k within K ...
let J[3] :=  4;
let t[3,6,4] := 364;

display K, I, J, t [3,6,4];

printf "--- expanding J: ------------------------------\n";
let J[3] :=  9;        # expanding J ...
let t[3,6,9] := 369;

display K, I, J, t[3,6,9];

printf "--- expanding K: ------------------------------\n";
let K := 6;            # expanding K ...
let I[K] :=  7;
let J[K] :=  9;

let t[K,6,9] := 669;

display K, I, J, t[6,6,9];
#==========================================================

[AMPL Google Group]

Writing "param t {k in 1..K, i in 1..I[k], j in 1..J[k]};" is only worthwhile if you are going to fill up all of the I[k]-by-J[k] matrices. If you fill in only some of the values, then you will get errors when you try to index over {k in 1..K, i in 1..I[k], j in 1..J[k]} in your model. Moreover there's no AMPL syntax to index over something like {k in 1..K, i in 1..I[k], j in 1..J[k]: "t[k,i,j] exists"}. Instead you will want to use a "sparse matrix" structure as Paras originally mentioned. For example you could specify

param K;
param I {1..K};
param J {1..K};

set KIJ within {k in 1..K, i in 1..I[k], j in 1..J[k]};
param t {KIJ};

Then KIJ is a set of triples that contains a member (k,i,j) for each position (i,j) within matrix k where there is actually a number. No storage is allocated by "set KIJ within . . ." until you add some triples to it by, say,

let KIJ := {};

let KIJ := KIJ union {(2,6,4)};

let t[2,6,4] := 264;

let KIJ := KIJ union {(3,6,4)};

let t[3,6,4]:= 364;

--
Robert Fourer
am...@googlegroups.com

{#HS:567993197-6048#}

[Peter Greistorfer]

Thank you! I believe, I got your message ... essentially. Already noticed, indexing over empty "spaces" won't work, but on the other side I cannot totally see your argument that I[k]-by-J[k] matrices are only useful if they are filled: (1) If I know, where a single value is located within such a, say, 3-by-2 area, and if I don't need more values on that "level" (=k), then I'd saved the storage of 5 numbers. Is this picture wrong? Or is this true: I can directly acces a single value (if I know where it is), but, nevertheless, overall storage still remains that one for 6 numbers!? (probably, this is the correct picture ...) And, (2), another advantage is given by the different dimensions, I can have: 3-by-5 on k=1 and 2-by-2 on k=2, all in all using the storage of 19 numbers ... right?

Are there any means to release storage, e.g. reducing K to K-1, in order to free and forget my I[K]-by-J[K] area?

And - excuses, this is absolutely thrilling - are there any commands to show the memory occupied - or even to manage it?

Finally, thanks for your storage suggestion, which is actually sparse!

[AMPL Google Group]

It's true that if you define "param t {k in 1..K, i in 1..I[k], j in 1..J[k]};" and then assign only a few of the values in some of the I[k]-by-J[k] matrices, then AMPL will allocate space for only the values that you have assigned. However to later make use of those values, you'll need to keep track of where they are, which is basically the function of the set KIJ in my example.

I should note that another way to define your sparse data is to define

param K;
param I {1..K};
param J {1..K};

set IJ {k in 1..K} within {i in 1..I[k], j in 1..J[k]};
param t {k in 1..K, (i,j) in IJ[k]};

Then IJ[k] is a set of pairs that contains a member (i,j) for each position within matrix k where there is actually a number. In this case, no storage is allocated by "set IJ {k in 1..K} within . . ." until you add some pairs to some of the sets IJ[k] by, say,

let {k in 1..K} IJ[k] := {};

let IJ[2] := IJ[2] union {(6,4)};

let t[2,6,4] := 264;

let IJ[3] := IJ[3] union {(5,2)};
let t[3,5,2]:= 352;

Whether you use this or the other setup with a set KIJ of triples is just a matter of your preference and convenience; either way, t ends up having 3 subscripts.

--
Robert Fourer
am...@googlegroups.com

{#HS:567993197-6048#}

On Fri, Apr 27, 2018 at 5:22 PM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Thank you! I believe, I got your message ... essentially. Already noticed, indexing over empty "spaces" won't work, but on the other side I cannot totally see your argument that I[k]-by-J[k] matrices are only useful if they are filled: (1) If I know, where a single value is located within such a, say, 3-by-2 area, and if I don't need more values on that "level" (=k), then I'd saved the storage of 5 numbers. Is this picture wrong? Or is this true: I can directly acces a single value (if I know where it is), but, nevertheless, overall storage still remains that one for 6 numbers!? (probably, this is the correct picture ...) And, (2), another advantage is given by the different dimensions, I can have: 3-by-5 on k=1 and 2-by-2 on k=2, all in all using the storage of 19 numbers ... right?

Are there any means to release storage, e.g. reducing K to K-1, in order to free and forget my I[K]-by-J[K] area?

And - excuses, this is absolutely thrilling - are there any commands to show the memory occupied - or even to manage it?

Finally, thanks for your storage suggestion, which is actually sparse!

On Fri, Apr 27, 2018 at 3:01 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Writing "param t {k in 1..K, i in 1..I[k], j in 1..J[k]};" is only worthwhile if you are going to fill up all of the I[k]-by-J[k] matrices. If you fill in only some of the values, then you will get errors when you try to index over {k in 1..K, i in 1..I[k], j in 1..J[k]} in your model. Moreover there's no AMPL syntax to index over something like {k in 1..K, i in 1..I[k], j in 1..J[k]: "t[k,i,j] exists"}. Instead you will want to use a "sparse matrix" structure as Paras originally mentioned. For example you could specify

param K;
param I {1..K};
param J {1..K};

set KIJ within {k in 1..K, i in 1..I[k], j in 1..J[k]};
param t {KIJ};

Then KIJ is a set of triples that contains a member (k,i,j) for each position (i,j) within matrix k where there is actually a number. No storage is allocated by "set KIJ within . . ." until you add some triples to it by, say,

let KIJ := {};

let KIJ := KIJ union {(2,6,4)};
let t[2,6,4] := 264;

let KIJ := KIJ union {(3,6,4)};
let t[3,6,4]:= 364;


--
Robert Fourer
am...@googlegroups.com

[Peter Greistorfer]

I noticed your answer a little late, thanks for your detailed explanations! - May I finally draw your attention to one question already sketched: so when I learned that memory-usage can be directly increased by extending ranges of arrays (e.g. by increasing I[k] and J[k]), and subsequently using that extension storage, is there also a way to release memory (e.g. erasing an array I[k] x J[k] for any k)?

[AMPL Google Group]

You can reset any of the IJ[k] sets back to the empty set. However if you already associated some data with that set, you will get a warning. Here's an example following on my previous definitions:

ampl: let IJ[2] := {};

ampl: display t;
Error executing "display" command:
error processing param t:
invalid subscript t[2,6,4] discarded.

t :=
3 5 2 352

This does not cause AMPL to return any memory to the operating system. However it does free up some space within AMPL's allocation, which AMPL can use later to store new members of the sets and new values of the parameter t.

--
Robert Fourer
am...@googlegroups.com

{#HS:567993197-6048#}

On Sun, May 6, 2018 at 7:31 PM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

I noticed your answer a little late, thanks for your detailed explanations! - May I finally draw your attention to one question already sketched: so when I learned that memory-usage can be directly increased by extending ranges of arrays (e.g. by increasing I[k] and J[k]), and subsequently using that extension storage, is there also a way to release memory (e.g. erasing an array I[k] x J[k] for any k)?

On Mon, Apr 30, 2018 at 6:15 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

It's true that if you define "param t {k in 1..K, i in 1..I[k], j in 1..J[k]};" and then assign only a few of the values in some of the I[k]-by-J[k] matrices, then AMPL will allocate space for only the values that you have assigned. However to later make use of those values, you'll need to keep track of where they are, which is basically the function of the set KIJ in my example.

I should note that another way to define your sparse data is to define

param K;
param I {1..K};
param J {1..K};

set IJ {k in 1..K} within {i in 1..I[k], j in 1..J[k]};
param t {k in 1..K, (i,j) in IJ[k]};

Then IJ[k] is a set of pairs that contains a member (i,j) for each position within matrix k where there is actually a number. In this case, no storage is allocated by "set IJ {k in 1..K} within . . ." until you add some pairs to some of the sets IJ[k] by, say,

let {k in 1..K} IJ[k] := {};

let IJ[2] := IJ[2] union {(6,4)};
let t[2,6,4] := 264;

let IJ[3] := IJ[3] union {(5,2)};
let t[3,5,2]:= 352;

Whether you use this or the other setup with a set KIJ of triples is just a matter of your preference and convenience; either way, t ends up having 3 subscripts.

--
Robert Fourer
am...@googlegroups.com

[Peter Greistorfer]

A fine closing remark - thanks a lot!