[Scip] which SCIP data structure for sparse 2d array of pointers

[Gregor Hendel]

Hi James,

as far as I know, there is no such central sparse data structure in 
SCIP, although there are some
places in the code, eg. heur_shiftandpropagate, where we use sparse 
matrices for a particular purpose.

A hash table seems to be indeed the best solution regarding your 
objectives implementation effort
and speed of look-ups, and the memory overhead is bearable and a vast 
improvement over
the quadratic effort of the matrix.

Best regards,
Gregor


Am 11.03.2015 um 12:08 schrieb James Cussens:
> Dear SCIP team,
>
> In my SCIP project I have a 2-dimensional (square) array of pointers.
> Each pointer is either NULL or a SCIP variable. This is OK if the
> dimensions of the array are, say, 10x10, since the waste of storing
> perhaps quite a few NULL pointers is bearable.
>
> However, once we move to, say, 1000x1000 this is no good. The good
> news is that for bigger cases like this most pointers will be NULL (ie
> for most i,j pairs there is no SCIP variable).
>
> I've been looking at which SCIP data structure to use for this (I am,
> of course, too lazy to implement my own). Possibilities seem to be
> hashtable or perhaps some sort of sortedvec? I would appreciate some
> advice on which is most sensible. Speed of lookup (without using
> memory stupidly) is more important to me than simplicity.
>
> Thanks,
>
> James
>