pulp and memory usage

[Frank Olaf Sem-jacobsen]

Hi,

I am attempting to use Python and pulp to generate very large LP
problems, with thousands upon thousands of constraints. For some of my
larger problems I have hit the memory roof of the machine I'm running
on, a 64-bit linux installation with 64 GB of RAM.

I obviously need to do some memory optimisations, but I am not sure
where to begin.

As far as I understand, pulp seems to keep the entire problem in
memory while I am generating it. An obvious optimisation would
therefore be to write the problem incrementally to a file (disk space
is cheaper than RAM), but I am not sure how easily this can be
modified in into the existing code? Another challenge with this is
that although it would work well with the CBC command line solver
(because it reads the problem from file) I am not quite sure how this
will work with gurobi which I am using now.

My best guess is that gurobi has its own place in library which pulp
hooks into in some fashion. How would I go about doing some memory
optimisations for this?

One of these documentation I am working on is to shorten the variable
names. These are currently around 40 characters to make the decoding
easy.

On a side note, I just started testing gurobi in the Amazon cloud and
I find this a very efficient and affordable way of testing this
solver :-)

If it helps, I could probably attach an example problem description
file, although this would be quite large for the large problems I am
looking at.

Thanks in advance for any help you can offer.

Regards,
Frank Olaf Sem-Jacobsen

[Stuart Mitchell]

Hmm that is a lot a memory,

If the problem formulation is correct (i.e. smaller problems solve ok)

I would recommend moving directly to the Gurobi python interface and see if Gurobi itself can solve it.

This will cut your memory footprint in half.

If Gurobi can solve the problem and you still want to use pulp I can look at the memory usage.

Stu

--
You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.
To post to this group, send email to pulp-or...@googlegroups.com.
To unsubscribe from this group, send email to pulp-or-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/pulp-or-discuss?hl=en.

--

Stuart Mitchell

PhD Engineering Science

Extraordinary Freelance Programmer and Optimisation Guru

www.stuartmitchell.com

[Yaron Kretchmer]

Frank Olaf-

 

saving and restoring memory to/from disk is a standard feature of linux, through a process called swapping.

 

I think your focus should be on why are you getting such an extremely high memory footprint in the first place.

 

Yaron

[Frank Olaf Sem-jacobsen]

Thanks for the suggestion, I have been considering doing that, but
that probably means I had to change all my code that formulates the
constraints etc. I would therefore prefer to find a solution through
some change in the pulp library instead :-)

--
Frank Olaf Sem-Jacobsen

[Frank Olaf Sem-jacobsen]

Thank you for your response.

I'm well aware of how swapping works, and the performance hit it
incurs. This is precisely reason why I want to find some other
solution to deal with the large memory problem.

The reason for the large memory requirements is because the problem is
large, with thousands of variables. We have already gone several
rounds of optimising the problem size to allow us to scale as much as
possible within our current limits.

While I am on the subject, how much space is contributed by the
variable name? Say if I half the size of the variable names, will this
half the memory requirements?

Thanks.
Frank Olaf

--
Frank Olaf Sem-Jacobsen

[Christophe-Marie Duquesne]

On Thu, Mar 22, 2012 at 11:24 AM, Frank Olaf Sem-jacobsen
<fran...@ifi.uio.no> wrote:
>
> I would therefore prefer to find a solution through
> some change in the pulp library instead :-)

Hi Olaf,

Right now pulp solves problems by copying it to the targeted solver:
- If the targeted solver is commandline, the problem is written to a
file and then the solver is spawned and the output parsed.
- If the targeted solver is reached from a library, the problem is
formulated using the solver's API, and the values are retrieved from
this API after the solve.

This can't be worked around without changing the API. Why? Consider
this example from the project page:

# Build the problem: At this point pulp is not aware of what
solver is to be used
x = LpVariable("x", 0, 3)
y = LpVariable("y", 0, 1)
prob = LpProblem("myProblem", LpMinimize)
prob += x + y <= 2
prob += -4*x + y

# Solve it: that is where you tell pulp your solver of choice.
status = prob.solve(GLPK(msg = 0))

So because you don't specify the solver when you formulate the
problem, but only at solve time, pulp can't write directly in the
solver's memory on the fly, thus the duplication.

If you really want a chance to reduce your memory footprint, you
should probably use a different API...

[Stuart Mitchell]

Hmm I think if you look at the python api for gurobi you would find that it is very similar to pulp syntax,

So much so that you can probably change your code using find and replace only :-).

The only other thing I can suggest at the moment is that you may have an error in your code. Specifically if you treat a list or dictionary of variables as a single variable in Pulp i.ie add it to a constraint, you get high memory usage.

Stu

Sorry for the late reply found this unfinished email lying around

[Matthew Pearlson]

Hi Stuart and others.

I am finding a similar problem on my side.

We have a pulp problem that solves fine for smaller scenario. However, when we try and run on a larger problem it hangs during the constraint creation step after exceeding the system RAM (16 GB). 

Are there general suggestions for optimization you could point us to? Thanks! Matthew

[Stuart Mitchell]

http://www.stuartmitchell.com/journal/2012/2/3/my-top-n-tips-for-python-coding-in-optimisation-1.html

May help

Stu

Stuart Mitchell

PhD Engineering Science

Extraordinary Freelance Programmer and Optimisation Guru

www.stuartmitchell.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 post to this group, send email to pulp-or...@googlegroups.com.

Visit this group at https://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/d/optout.

[Krishna Kottakki]

Please look into the possibilities of decomposing the problem, wherever possible.

Regards,

Krishna 

--
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 post to this group, send email to pulp-or...@googlegroups.com.