• No replies
1883 Posts

Pinned topic run time implications of generic array access with tuples

‏2013-01-05T22:06:07Z |
The "exploiting sparsity" section of the OPL Language Users manual is a bit vague.

In particular, the sentence

"In addition, the aggregate operator on the second line
sum(<p,o,d> in Routes) trans<p,o,d> <= capacity;
cannot exploit the “connection” structure to obtain all products of a connection, since o and
d are separate entities."

Could stand for some additional explanation.

When I compare

ctCapacity: forall( o , d in Cities )
sum( <p,o,d> in Routes )
Trans<p,o,d> <= Capacity;


forall(c in Connections)
sum( <p,c> in Routes )
Trans<p,c> <= Capacity;

It seems clear why there is a potential for run time improvement in the foall statement. The first forall statement iterates over all pairs, and the second over relevant pairs.

However, it is unclear why sum( <p,c> in Routes ) might run much faster than sum( <p,o,d> in Routes ). In the former case, we are looking up all the p entries for a given c. In the latter, we are looking up all the p entries for a given o,d pair. If the Connections array contains nearly all o,d pairs, but each pair only uses a small number of the possible p elements, will the second code block still run much faster? And, if so, why? Is OPL simply more efficient at looking up two-element-tuples where one is known than it is with 3-element tuples where two elements are known?

Does OPL do something analogous to creating a single-field index in the generic array for each entry of the tuple? And so, if one entry of the tuple is known (even if that entry is itself a tuple) than it can quickly find the matching elements of the generic array. But this speed is lost when the search is based on multiple known tuple elements, even if the underlying search results are effectively identical.

I'm helping a Kellog B school prof put together a course that is partially based on OPL, so I'd like to be able to describe the performance implications in a somewhat rigorous way.

Thanks for any help. The course is 3 weeks out, so no huge rush.