MemoryError

[Tim Klein]

Hi,

I'm trying to solve minimum / maximum commute problems for a number of regions (for background, if you're interested: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.462.5089&rep=rep1&type=pdf). For such a problem, I have a cost matrix, a matrix of observed commuter flows, and row- and column-sums as constraints. Objective is to minimize or maximize the total cost by adjusting the commuter flows (m_commute below).

It all works very well with Pulp, cbc and glpk until i get to a matrix size of sqr(1764), where pulp throws a memory error (on my laptop, on my office computer (python 37-32) and on the amazon Linux AMI 2018.03.0 (python 36) as well):

    LpProb += lpSum(cost[i,j] * m_commute[i][j] for i in I for j in J)
  File "C:\Program Files (x86)\Python37-32\lib\site-packages\pulp\pulp.py", line 2046, in lpSum
    return LpAffineExpression().addInPlace(vector)
  File "C:\Program Files (x86)\Python37-32\lib\site-packages\pulp\pulp.py", line 739, in addInPlace
    self.addInPlace(e)
  File "C:\Program Files (x86)\Python37-32\lib\site-packages\pulp\pulp.py", line 732, in addInPlace
    self.addterm(v, x)
  File "C:\Program Files (x86)\Python37-32\lib\site-packages\pulp\pulp.py", line 617, in addterm
    self[key] = value
MemoryError

That's before adding constraints. No mps file created. Any ideas?

Thanks, Tim

[Sean Grogan]

when you mention a size sqrt(1764) matrix, you mean it's a matrix 42x42? Because that seems like a trivial size and you may have some problems outside of your code. 

If you're stuck using 32 bit python, consider using a '2D dict' (like cost[i][j] * m_commute[i][j]) as they will typically be smaller/faster.  Otherwise, 64bit python will have a higher memory limit

Sean Grogan
sean....@gmail.com

--
New posters to this group are moderated which can take up to 48 hours, so please be patient if your first post takes a while to turn up.
---
You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pulp-or-discuss/a27cabbc-cd9f-4748-99ff-694f31ae1c99o%40googlegroups.com.

[Tim Klein]

Hi,

thanks for the input. It is "sqr(1764)" = 3.111.696‬ variables, and to examine similar issues i'd like to go up to maybe 3000x3000, a not too uncommon matrix size for a metropolitan transport demand model. The amazon machine image i tried runs 64bit python36 and gives a memory error even before starting the pulp module, while reading the commute matrix.

Do you suggest replacing the definition of the objective from

    LpProb += lpSum(cost[i,j] * m_commute[i][j] for i in I for j in J)

to

    LpProb += lpSum(cost[i][j] * m_commute[i][j] for i in I for j in J)

- that just gave me:

...

  File "C:\xyz.py", line 155, in <genexpr>
    LpProb += lpSum(cost[i][j] * m_commute[i][j] for i in I for j in J)
KeyError: 0

which i don't understand either, I an J are just range(1764) objects.

Am Sonntag, 7. Juni 2020 23:47:40 UTC+2 schrieb Sean Grogan:

when you mention a size sqrt(1764) matrix, you mean it's a matrix 42x42? Because that seems like a trivial size and you may have some problems outside of your code. 

If you're stuck using 32 bit python, consider using a '2D dict' (like cost[i][j] * m_commute[i][j]) as they will typically be smaller/faster.  Otherwise, 64bit python will have a higher memory limit

Sean Grogan
sean....@gmail.com

On Sun, Jun 7, 2020 at 5:15 PM Tim Klein <tristra...@gmail.com> wrote:

Hi,

I'm trying to solve minimum / maximum commute problems for a number of regions (for background, if you're interested: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.462.5089&rep=rep1&type=pdf). For such a problem, I have a cost matrix, a matrix of observed commuter flows, and row- and column-sums as constraints. Objective is to minimize or maximize the total cost by adjusting the commuter flows (m_commute below).

It all works very well with Pulp, cbc and glpk until i get to a matrix size of sqr(1764), where pulp throws a memory error (on my laptop, on my office computer (python 37-32) and on the amazon Linux AMI 2018.03.0 (python 36) as well):

    LpProb += lpSum(cost[i,j] * m_commute[i][j] for i in I for j in J)
  File "C:\Program Files (x86)\Python37-32\lib\site-packages\pulp\pulp.py", line 2046, in lpSum
    return LpAffineExpression().addInPlace(vector)
  File "C:\Program Files (x86)\Python37-32\lib\site-packages\pulp\pulp.py", line 739, in addInPlace
    self.addInPlace(e)
  File "C:\Program Files (x86)\Python37-32\lib\site-packages\pulp\pulp.py", line 732, in addInPlace
    self.addterm(v, x)
  File "C:\Program Files (x86)\Python37-32\lib\site-packages\pulp\pulp.py", line 617, in addterm
    self[key] = value
MemoryError

That's before adding constraints. No mps file created. Any ideas?

Thanks, Tim

--
New posters to this group are moderated which can take up to 48 hours, so please be patient if your first post takes a while to turn up.
---
You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or...@googlegroups.com.

[Stuart Mitchell]

Hi Tim that is a large matrix,

I would start my only storing non-zero OD pairs i.e 

lpSum(cost[i,j] * m_commute[i][j] for i, j in NonZeros)

I found when I was doing OD modelling I actually set a higher cut off (than 0) to eliminate the complexity

Stu

Stuart Mitchell

PhD Engineering Science

Extraordinary Freelance Programmer and Optimisation Guru

www.stuartmitchell.com

To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pulp-or-discuss/bc9d1574-8dd7-4cea-a613-51b0aadfb590o%40googlegroups.com.

[Tim Klein]

Hi Stu,

thanks! i'll definitely try that, maybe using some more filters (e.g. cost above or below average for minimum/maximum commute). Just to make sure, that means the relations with 0 commute left out of the objective will remain zero and have to be combined with the solution to make the final result?

I am looking at 88 regions in total, out of which 78 had no problems. So i can compare results for these 78. I'll report...

best, t

Am Dienstag, 9. Juni 2020 00:16:24 UTC+2 schrieb Stuart Mitchell:

Hi Tim that is a large matrix,

I would start my only storing non-zero OD pairs i.e 

lpSum(cost[i,j] * m_commute[i][j] for i, j in NonZeros)

I found when I was doing OD modelling I actually set a higher cut off (than 0) to eliminate the complexity

Stu

Stuart Mitchell

PhD Engineering Science

Extraordinary Freelance Programmer and Optimisation Guru

www.stuartmitchell.com

To view this discussion on the web visit https://groups.google.com/d/msgid/pulp-or-discuss/bc9d1574-8dd7-4cea-a613-51b0aadfb590o%40googlegroups.com.

[Tim Klein]

Update: I did a sort of 'Hail Mary' and installed a new python version on my laptop - 3.8.3 64bit - and now it worked, the largest matrix being 2114*2114. It'll be interesting to try Stu's suggestion, however, as i noticed the solutions for either minimisation or maximisation had only few nonzero values, e.g. just over 4.000 for the largest matrix.