Ask Your Question
1

Memory blowup with MILP

asked 2012-02-21 06:56:23 -0500

G-Sage gravatar image

updated 2012-03-07 02:08:26 -0500

Hello, I have been running some code on our Sage server and it ends up using a huge amount of memory, up to around 50 GB, and then eventually stops running. No error message is generated. It's just that the green bar is gone and it isn't doing anything. This code should generate the problem. When I ran this, it ran up to around 300,000 graphs and then stopped. It should run through all 12.7 million without stopping.

count = 0

for g in graphs.nauty_geng("10"):
    count = count + 1
    if count % 50000 == 0:
        print count
    vcc = int(round(g.complement().chromatic_number(algorithm = "MILP")))
    if vcc == 9:
        print g.graph6_string()

Now, I talked to Jason Grout later and he mentioned that if I changed it to algorithm = "CP", not only does the memory problem not occur, it is also faster on smaller graphs. But, there is still the problem with the MILP algorithm that should be addressed at some point, I assume.

Thanks

UPDATE: I tried the gc.collect() and want to say it doesn't do anything.

g = graphs.PetersenGraph()
for count in [1..100000]:
    if count % 5000 == 0:
        print count
        print get_memory_usage()
        gc.collect()
        print get_memory_usage()
    test = g.independent_set()

the get_memory_usage() keeps getting higher and higher and higher as I do this. The way I got it to reset was to save and quit the worksheet.

Not a huge deal because we have a better fix coming, it appears. But, just wanted to point out that gc.collect() doesn't seem to do anything as far as I can tell.

UPDATE 2: The patch didn't work. There is still a memory leak. Here is the exact code I am running this time, after the patch was installed to our Sage server.

count = 0

for g in graphs.nauty_geng("10"):
    if count % 50000 == 0:
        print count
        print get_memory_usage()
    count = count + 1

    vcc = int(round(g.chromatic_number("MILP")))

The memory usage at 0 was 808. At 50000, it was 3145. At 100000, it was 8106. At 200000, we're up to 14369.

edit retag flag offensive close merge delete

Comments

I can confirm those numbers with the patch up at #12616. I also tried without the patch and got a memory usage of 3209 at 50000, so it looks like maybe things are slightly better with the #12616 patch, but not much better.

Jason Grout gravatar imageJason Grout ( 2012-03-10 02:55:53 -0500 )edit

3 answers

Sort by ยป oldest newest most voted
3

answered 2012-03-01 08:00:34 -0500

Nathann gravatar image

Well, it turns out that there is "nothing wrong" except that the garbage collector is not our friend on that one... The code is ok but some objects are not freed from the memory even when they are not useful anymore, and the developpers on sage-devel advised to call the following code :

import gc
gc.collect()

They also seemed to say that calling gc.collect() was a time-consuming operation, so I guess that in your situation the best option is ti call gc.collect() every 1000th run.

Something like that :

if count % 5000 == 0:
    gc.collect()

I do not like it, but it looks like it is the best situation available :-)

Nathann

edit flag offensive delete link more

Comments

Okay, I will try that. This is exactly what I was looking for. The memory usage grows slow enough that I could run this every 500,000 graphs or something. So, the time isn't much of an issue at all.

G-Sage gravatar imageG-Sage ( 2012-03-01 14:52:29 -0500 )edit

Well, actually there was a better fix to be found ! God I love Sage developpers :-)

Nathann gravatar imageNathann ( 2012-03-01 22:01:53 -0500 )edit

Here is the patch that fixes it definitively : http://trac.sagemath.org/sage_trac/ticket/12616

Nathann gravatar imageNathann ( 2012-03-01 22:02:23 -0500 )edit

@Nathann Awesome. Thanks so much. I will use the temporary fix of garbage collector until the next version of Sage comes out!

G-Sage gravatar imageG-Sage ( 2012-03-02 05:44:25 -0500 )edit

We could just patch your Sage server...

Jason Grout gravatar imageJason Grout ( 2012-03-02 19:48:08 -0500 )edit
2

answered 2012-02-29 02:34:06 -0500

Nathann gravatar image

updated 2012-02-29 02:34:43 -0500

Hmmmm.... Weird thing. I wrote to sage-devel about this problem at this address.

Nathann

edit flag offensive delete link more

Comments

Awesome, I appreciate it. It would be super sweet if this problem no longer existed, as far as what I am using Sage for :)

G-Sage gravatar imageG-Sage ( 2012-02-29 02:40:02 -0500 )edit
1

answered 2012-02-21 07:07:17 -0500

Nathann gravatar image

Helloooooooo !!

Could you tell us whether you have some optional LP solver installed (for instance Coin ?) and which version of Sage you are running ? We fixed such things recently, but perhaps we forgot some :-)

Nathann

edit flag offensive delete link more

Comments

CPlex is installed. It's Sage 4.8.

G-Sage gravatar imageG-Sage ( 2012-02-21 08:20:21 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-02-21 06:56:23 -0500

Seen: 471 times

Last updated: Mar 01 '12