Thread Subject: Optimization and memory issues

Hello!

I am solving large linear optimization problems with millions of variables and hundreds of thousands of constraints.
At the moment I am doing this using MATLAB with sparse matrices. Since MATLAB however stores all non-zero elements of the matrix as doubles, the matrices are still very big and I run into memory issues. I think there is no solution to that within MATLAB...

I am now wondering if I can get around this problem using C++ with CPLEX/ILOG.
Do you think this would help to overcome my memory issues?

Thanks,
Jay

On 8/1/2011 9:11 AM, Jay wrote:
> Hello!
>
> I am solving large linear optimization problems with millions of
> variables and hundreds of thousands of constraints.
> At the moment I am doing this using MATLAB with sparse matrices. Since
> MATLAB however stores all non-zero elements of the matrix as doubles,
> the matrices are still very big and I run into memory issues. I think
> there is no solution to that within MATLAB...
...

My understanding is that current versions of ML treat singles as a
full-fledged class for math operations so unless you are forced to
double for precision reasons that would double memory.

It's also possible that perhaps the 64-bit version might help???

I would guess you'll run into similar memory issues w/ 32-bit compilers
on 32-bit OS even w/ compiled languages; perhaps just a _bit_ later as
the data will still be the data.

--

dpb <none@non.net> wrote in message <j16d0f$n72$1@speranza.aioe.org>...
> On 8/1/2011 9:11 AM, Jay wrote:
> > Hello!
> >
> > I am solving large linear optimization problems with millions of
> > variables and hundreds of thousands of constraints.
> > At the moment I am doing this using MATLAB with sparse matrices. Since
> > MATLAB however stores all non-zero elements of the matrix as doubles,
> > the matrices are still very big and I run into memory issues. I think
> > there is no solution to that within MATLAB...
> ...
>
> My understanding is that current versions of ML treat singles as a
> full-fledged class for math operations so unless you are forced to
> double for precision reasons that would double memory.
>
> It's also possible that perhaps the 64-bit version might help???
>
> I would guess you'll run into similar memory issues w/ 32-bit compilers
> on 32-bit OS even w/ compiled languages; perhaps just a _bit_ later as
> the data will still be the data.
>
> --

hi dpd!
Are you saying that ML treats singles as a full-fledges class, so if I would not need double precision I could half memory somewhere else?
I guess float precision would be enough for my task..

64bit version is already in use, no gain there :-(

Thanks,
Jay

On 8/1/2011 9:43 AM, Jay wrote:
> dpb <none@non.net> wrote in message <j16d0f$n72$1@speranza.aioe.org>...
...

>> My understanding is that current versions of ML treat singles as a
>> full-fledged class for math operations so unless you are forced to
>> double for precision reasons that would double memory.
...

> Are you saying that ML treats singles as a full-fledges class, so if I
> would not need double precision I could half memory somewhere else?
> I guess float precision would be enough for my task..
...

I'm guessing somewhat about how newer versions treat
singles...documentation (as per usual) is somewhat obtuse and since I
don't have new version can't test what it does internally but here's the
link...

<http://www.mathworks.com/help/techdoc/matlab_prog/f2-12135.html#f2-108458>

_IF_ (the proverbial "big if") ML doesn't internally create temporary
working arrays as doubles to pass to the native functions, then if you
start w/ everything in your models as single() then you _should_ be able
to (nearly) double your problem size.

What I don't know is whether the above is so or not; used to be that
transparently what was implemented for the classes other than double did
get promoted then returned so actually cost memory during operations
even though the storage was halved. That was sorta' a useless model for
many purposes.

It would be better if there were the facility to declare variables or
declare a workspace as the desired precision rather than this nebulous
casting process...I've not used the new versions so not sure of the
details but there is at least a chance you'll probably want to explore
before you jump off into writing a lot of code.

Hopefully S Lord will jump in here and amplify the details...

--

"Jay" wrote in message <j16e1v$lvv$1@newscl01ah.mathworks.com>...
> dpb <none@non.net> wrote in message <j16d0f$n72$1@speranza.aioe.org>...
> > On 8/1/2011 9:11 AM, Jay wrote:
> > > Hello!
> > >
> > > I am solving large linear optimization problems with millions of
> > > variables and hundreds of thousands of constraints.
> > > At the moment I am doing this using MATLAB with sparse matrices. Since
> > > MATLAB however stores all non-zero elements of the matrix as doubles,
> > > the matrices are still very big and I run into memory issues. I think
> > > there is no solution to that within MATLAB...
> > ...
> >
> > My understanding is that current versions of ML treat singles as a
> > full-fledged class for math operations so unless you are forced to
> > double for precision reasons that would double memory.
> >
> > It's also possible that perhaps the 64-bit version might help???
> >
> > I would guess you'll run into similar memory issues w/ 32-bit compilers
> > on 32-bit OS even w/ compiled languages; perhaps just a _bit_ later as
> > the data will still be the data.
> >
> > --
>
> hi dpd!
> Are you saying that ML treats singles as a full-fledges class, so if I would not need double precision I could half memory somewhere else?

Assuming single-sparse would exist, you won't save even half memory, but 1/4 at best. The reason: See my post #7 of this thread:

http://www.mathworks.nl/matlabcentral/newsreader/view_thread/274955

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <j16gbj$rd$1@newscl01ah.mathworks.com>...
> "Jay" wrote in message <j16e1v$lvv$1@newscl01ah.mathworks.com>...
> > dpb <none@non.net> wrote in message <j16d0f$n72$1@speranza.aioe.org>...
> > > On 8/1/2011 9:11 AM, Jay wrote:
> > > > Hello!
> > > >
> > > > I am solving large linear optimization problems with millions of
> > > > variables and hundreds of thousands of constraints.
> > > > At the moment I am doing this using MATLAB with sparse matrices. Since
> > > > MATLAB however stores all non-zero elements of the matrix as doubles,
> > > > the matrices are still very big and I run into memory issues. I think
> > > > there is no solution to that within MATLAB...
> > > ...
> > >
> > > My understanding is that current versions of ML treat singles as a
> > > full-fledged class for math operations so unless you are forced to
> > > double for precision reasons that would double memory.
> > >
> > > It's also possible that perhaps the 64-bit version might help???
> > >
> > > I would guess you'll run into similar memory issues w/ 32-bit compilers
> > > on 32-bit OS even w/ compiled languages; perhaps just a _bit_ later as
> > > the data will still be the data.
> > >
> > > --
> >
> > hi dpd!
> > Are you saying that ML treats singles as a full-fledges class, so if I would not need double precision I could half memory somewhere else?
>
> Assuming single-sparse would exist, you won't save even half memory, but 1/4 at best. The reason: See my post #7 of this thread:
>
> http://www.mathworks.nl/matlabcentral/newsreader/view_thread/274955
>
> Bruno

Hey guys!

Bruno, you mean this?
 The non-zero elements are stored in Pr/Pi pointers, Pi is allocated for complex matrix ony, and NULL otherwise. The array(s) has(ve) NZMAX in length; and each element is a double (8 bytes) or logical (1 bytes).
- the integer array JC has (number of columns + 1) entries; JC contains the linear index (zero-based) of the first non-zero elements of the column. The last element of JC is therefore the total number of non-zeros of sparse matrix.
- The integer array IR has the same size as Pr/Pi (NZMAX) containing the row of the elements (zero-based).

Integer arrays (JC and IR) are 4/8 bytes depending where as your Matlab is an 32/64 bit version.


Dont really get that. So we have one array (JC) stores the column-indices of non zero elements, and another one (IR) the row indices. They are 4/8 bytes per element I guess respectively.
But where exactly is the data, the values itself stored?

And I dont see why that would limit me to have max 1/4 memory gain?


Other than that do you have any advice where to turn to figure stuff out about C++ and CPLEX? I can't find a mailinglist or forum for this...

Thanks,
Jay

"Jay" wrote in message <j16n8u$nuh$1@newscl01ah.mathworks.com>...
>
>
> But where exactly is the data, the values itself stored?

Pr (and possibly Pi if the matrix is complex).

>
> And I dont see why that would limit me to have max 1/4 memory gain?
>

Because on 64-bit platform
1. sizeof (Pr + JC) = 16*nzmax bytes for double
2. sizeof (Pr + JC) = 12*nzmax bytes for single

The saving would be 1/4 (not 1/2) in byte-size.

>
> Other than that do you have any advice where to turn to figure stuff out about C++ and CPLEX? I can't find a mailinglist or forum for this...
>

Sorry I don't know what you mean by "figure stuff" and by "turn to". Do you refer to another thread?

Bruno

"Jay" wrote in message <j16c6f$fs1$1@newscl01ah.mathworks.com>...
> Hello!
>
> I am solving large linear optimization problems with millions of variables and hundreds of thousands of constraints.
> At the moment I am doing this using MATLAB with sparse matrices. Since MATLAB however stores all non-zero elements of the matrix as doubles, the matrices are still very big and I run into memory issues. I think there is no solution to that within MATLAB...
=================


Keep in mind also that wide sparse matrices can consume a lot more memory than tall ones. This is illustrated by my favorite example below.

>> wide=spalloc(1,1e6,1);
>> tall=wide.';

>> whos wide tall
  Name Size Bytes Class Attributes

  tall 1000000x1 20 double sparse
  wide 1x1000000 4000016 double sparse


This makes me wonder whether you could save some memory by solving the dual linear program, which would have a tall system matrix as opposed to a wide one.

 Hi guys!

Interesting point with the wide and tall matrices, I will have a look into that :-)

"Jay" wrote in message <j18ja5$dao$1@newscl01ah.mathworks.com>...
> Hi guys!
>
> Interesting point with the wide and tall matrices, I will have a look into that :-)

Use my post about size of sparse matrix to calculate exactly how much memory you need.

Personally I think when you start to run out of memory like this, there is not much that you can do. The difference between tall and flat is JC, which can save 1/3 in size for fully populated matrix. Then we don't know what behind the scene of linear programming (you did not tell us how you solve the linear optimization problem, and where exactly in the process the memory problem occurs).

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <j18p3p$spo$1@newscl01ah.mathworks.com>...
>
>
> Personally I think when you start to run out of memory like this, there is not much that you can do. The difference between tall and flat is JC, which can save 1/3 in size for fully populated matrix.
====================

Not sure I understood that point, Bruno. Clearly, when using sparse type, you normally aren't working with a fully populated matrix. And when it's not fully populated, the memory savings between tall and wide can be much greater than 1/3, as my example showed.

"dpb" <none@non.net> wrote in message news:j16eut$see$1@speranza.aioe.org...
> On 8/1/2011 9:43 AM, Jay wrote:
>> dpb <none@non.net> wrote in message <j16d0f$n72$1@speranza.aioe.org>...
> ...
>
>>> My understanding is that current versions of ML treat singles as a
>>> full-fledged class for math operations so unless you are forced to
>>> double for precision reasons that would double memory.
> ...
>
>> Are you saying that ML treats singles as a full-fledges class, so if I
>> would not need double precision I could half memory somewhere else?
>> I guess float precision would be enough for my task..
> ...
>
> I'm guessing somewhat about how newer versions treat
> singles...documentation (as per usual) is somewhat obtuse and since I
> don't have new version can't test what it does internally but here's the
> link...
>
> <http://www.mathworks.com/help/techdoc/matlab_prog/f2-12135.html#f2-108458>

That's the right link. However, this probably won't work for the OP because
they indicated they're using sparse matrices and only sparse logical and
sparse double matrices are allowed in MATLAB. [Logical arrays used to be
double arrays with the logical attribute, which is why many operations that
work on doubles also work more or less on logical arrays.]

> _IF_ (the proverbial "big if") ML doesn't internally create temporary
> working arrays as doubles to pass to the native functions, then if you
> start w/ everything in your models as single() then you _should_ be able
> to (nearly) double your problem size.

While the OP could obtain some increase if they could switch to single,
since they're using sparse matrices that's not possible. I'm also not
certain to what extent the Optimization Toolbox routines support single
precision; I'm not sure many (any?) do because it would require careful
handling of things like termination tolerances and I don't think there's
been all that many user requests for that support.

> What I don't know is whether the above is so or not; used to be that
> transparently what was implemented for the classes other than double did
> get promoted then returned so actually cost memory during operations even
> though the storage was halved. That was sorta' a useless model for many
> purposes.
>
> It would be better if there were the facility to declare variables or
> declare a workspace as the desired precision rather than this nebulous
> casting process...

? I'm not quite sure what you're asking.

x = single(1:10);
whos x
% or
x = single(1):10;
whos x
% or
x = single(1):single(10);
whos x

Any of these should make a single precision vector containing the integer
values between 1 and 10 inclusive; if you're really concerned and want to
ensure that we don't construct 1:10 then convert to single then you'd use
the last approach.

> I've not used the new versions so not sure of the details but there is at
> least a chance you'll probably want to explore before you jump off into
> writing a lot of code.
>
> Hopefully S Lord will jump in here and amplify the details...

Hopefully this clarifies some of the details.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

"Matt J" wrote in message <j1908h$sjo$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message

> Not sure I understood that point, Bruno. Clearly, when using sparse type, you normally aren't working with a fully populated matrix. And when it's not fully populated, the memory savings between tall and wide can be much greater than 1/3, as my example showed.

By "fully populated" I mean there is at least one non-zero element for each row and for each column. I believe in this case you won't have 1/3 of difference (I did not check).

Bruno

may I summarize some things? I am not quite certain if I can follow..

- single precision with sparse matrices would yield a memory reduction of max 1/4. However single sparse matrices are not supported by matlab.

- tall matrices need (if they are fully populated) up to 1/3 less memory than wide ones. If you however require the solver to get the data in the "wide-format" there would be no memory gain here as well


-> in matlab there is currently no way to reduce memory consumption when working with sparse matrices.

On 8/2/2011 9:48 AM, Steven_Lord wrote:
...
> That's the right link. However, this probably won't work for the OP
> because they indicated they're using sparse matrices and only sparse
> logical and sparse double matrices are allowed in MATLAB....

> While the OP could obtain some increase if they could switch to single,
> since they're using sparse matrices that's not possible. I'm also not
> certain to what extent the Optimization Toolbox routines support single
> precision; I'm not sure many (any?) do because it would require careful
> handling of things like termination tolerances and I don't think there's
> been all that many user requests for that support.

Indeed, I did forget while writing (waxing poetic? :) ) about the sparse
matrix problem--mea culpa there...

...

>> It would be better if there were the facility to declare variables or
>> declare a workspace as the desired precision rather than this nebulous
>> casting process...
>
> ? I'm not quite sure what you're asking.
>
> x = single(1:10);
> whos x
> % or
> x = single(1):10;
> whos x
> % or
> x = single(1):single(10);
> whos x
>
> Any of these should make a single precision vector containing the
> integer values between 1 and 10 inclusive; if you're really concerned
> and want to ensure that we don't construct 1:10 then convert to single
> then you'd use the last approach.

What I was saying was there (imo) there should be a way to say

single x

and then

x=1:10;

would be equivalent to

x = single(1):single(10);

as well as all references to x would be assured to not cause
intermediates of double silently which then again might be converted
back w/ that overhead as well.

I'm reverting somewhat back to languages that are more strongly
explicitly typed which is, granted, an idea that ML tried to avoid the
need for in its inception in search of the holy grail of
simplified/rapid development (with which I don't fault at all; I'm not
trying to do Monday-morning qb'ing or saying it was wrong and shouldn't
have been that way to begin with).

What it seems to me is that over the years ML has evolved from where it
was originally with everything a double array (matrix) to now include
multiple data types and data structures as well as aspects of OOP and so
on to try to keep pace with other languages (again, all well and good
and necessary, it's not the ideas I'm arguing). _BUT_, I'm not
convinced that implementing single as is only by requiring that every
variable be cast in use was the ideal way for implementation; I'd have
preferred (I think) the attribute assignment approach for variables or
even for a session. I think it would have cleaned up coding
significantly. It's also probably too late to change (and it might not
have been practical anyway).

--


>
>> I've not used the new versions so not sure of the details but there is
>> at least a chance you'll probably want to explore before you jump off
>> into writing a lot of code.
>>
>> Hopefully S Lord will jump in here and amplify the details...
>
> Hopefully this clarifies some of the details.
>

Try to use TOMLAB /CPLEX or one of the other LP solvers. If you have a
64-bit machine it should solve without a problem.

All the best, Marcus
http://tomopt.com/
http://tomsym.com/

"Marcus M. Edvall" <edvall@gmail.com> wrote in message <6fd9477c-3ecc-4210-a4c2-2999a61a1294@y39g2000prd.googlegroups.com>...
> Try to use TOMLAB /CPLEX or one of the other LP solvers. If you have a
> 64-bit machine it should solve without a problem.
>
> All the best, Marcus
> http://tomopt.com/
> http://tomsym.com/


Hi Marcus,

what makes you believe that using TOMLAB/CPLEX as solver could reduce my memory consumption? I will always need a sparse coefficient matrix, which requires a lot of memory.

Does CPLEX somehow for example use less memory than the function linprog() of MATLAB?

Jay,

Let me reiterate my question: Please tell us in detail when you run out of the memory (I don't believe you have).

Some (third party) linear programming solver can accept file as input (such as MPS format, etc...).

Bruno

Hi Jay,

You try TOMLAB /CPLEX and many other options. I assume you have memory
issues when solving the problem, not creating it.

All the best, Marcus
http://tomopt.com/

TOMLAB /CPLEX will use a lot less memory than linprog.

You can set parameter MEMORYEMPHASIS to reduce the usage further.

I recommend you try all LPMETHOD options and check the memory usage.

Best wishes, Marc
http://tomsym.com

>
> what makes you believe that using TOMLAB/CPLEX as solver could reduce my memory consumption? I will always need a sparse coefficient matrix, which requires a lot of memory.
>
> Does CPLEX somehow for example use less memory than the function linprog() of MATLAB?