Ask Your Question

Sage stalls during computation

asked 2019-10-11 02:27:37 -0500

Szabolcs gravatar image

updated 2020-06-01 04:41:02 -0500

FrédéricC gravatar image

I was using SageMath 8.8's feedback_edge_set function on a large dataset. The calculation would take a couple of days to finish.

Unfortunately, Sage would keep stalling every few hours. The CPU usage of the process would simply drop to zero, and it would stop doing anything. I had to kill the process (a simple kill worked, no kill -9 necessary).

Has anyone else experienced this? Is it a known problem? Is there a workaround? It is very frustrating to have to keep manually killing and restarting the process. This problem also prevents me from running a calculation overnight: in the morning I might find that it stopped merely an hour after I started it (if I'm unlucky).

More information:

  • I was using Sage on Linux
  • This function uses MixedIntegerLinearProgram. I used the default GLPK (didn't change settings)
  • I used alarm() to set a time limit on each computation.
  • I always believed GLPK not to be interruptible, so I am not even sure which interruption (either manual or alarm) work on Sage with this function. This may be relevant.
  • The memory usage of the process stayed low. It did not stall because the memory got filled and the machine started swapping.

Minimal example:

Put this in a source file:

import datetime
while True:
        fes = dg.feedback_edge_set()
    except AlarmInterrupt:
    i = i+1

Run it as sage sourcefile.sage.

In my last test, it took 291 iterations and ~4-5 hours before it stalled.

It appears to stall only when GLPK is used as the MIP solver (i.e. feedback_edge_set(solver='GLPK'), which is also the default). If I use solver='Coin' (which needs to be installed first using sage -i cbc) then it does not stall. However, the calculation is several times slower with Coin than with GLPK.

edit retag flag offensive close merge delete


Could you please isolate the graph that causes the issue and see if it is reproducible when the method is applied on that graph ?

tmonteil gravatar imagetmonteil ( 2019-10-12 14:58:16 -0500 )edit

You can provide a short string representation of your graph with:

sage: G.dig6_string()
tmonteil gravatar imagetmonteil ( 2019-10-12 16:29:20 -0500 )edit

@tmonteil It's not because of a specific graph. The stalling appears to be random. I know this because I normally run this on a set of pre-computed graphs, so I could easily re-try on the graph where it stalled. Also, running it twice on the same data won't stall at the same step.

Szabolcs gravatar imageSzabolcs ( 2019-10-13 04:59:34 -0500 )edit

aha, i was trying to idendify the culprit graphs.

tmonteil gravatar imagetmonteil ( 2019-10-13 11:00:05 -0500 )edit

2 answers

Sort by » oldest newest most voted

answered 2019-10-21 06:37:50 -0500

Szabolcs gravatar image

updated 2019-10-21 06:38:33 -0500

This looks like a bug in Sage or Sage's GLPK interface.

The practical solution that worked for me was to run the calculation in a separate process using Sage's parallelization features. It can be done by wrapping the feedback arc set calculation with a few function that has the @fork or @parallel decorators.

I can confirm that even after a several-day running time, the calculation has not stalled.

edit flag offensive delete link more

answered 2019-10-11 03:55:26 -0500

tmonteil gravatar image

updated 2019-10-11 03:57:45 -0500

I do not know the issue, but as a workaround, you can try:

sage -i cbc

and restart the computation.

Also, could you please provide the whole code so that someone can try to reproduce the issue ?

edit flag offensive delete link more


It is not that trivial to boil down the code to a minimal example. If I put in the work to do that, would you be willing to try to reproduce the problem? Trying to reproduce would also be some trouble: It would involve leaving Sage running for up to a day (or running multiple Sage processes for several hours to increase the likelihood that one of them would stall).

Szabolcs gravatar imageSzabolcs ( 2019-10-11 04:00:38 -0500 )edit

Could you reproduce the problem with a large random digraph ?

tmonteil gravatar imagetmonteil ( 2019-10-11 04:57:42 -0500 )edit

You can choose among different models:

sage: digraphs.Random<TAB_COMPLETION>
tmonteil gravatar imagetmonteil ( 2019-10-11 04:59:38 -0500 )edit

Sure—I'll get back to you when I have a small example that reliably fails. It'll take time as it usually takes hours for it to fail.

Szabolcs gravatar imageSzabolcs ( 2019-10-11 13:07:27 -0500 )edit

Some comments on sage -i cbc: this appears to set the default_mip_solver() to "Coin", but feedback_edge_set still uses GLPK by default. I can set it to use Coin manually, but GLPK is far faster. GLPK is also much faster than Gurobi when using this specific function. Perhaps this function uses some feature which is GLPK-specific and that's why it'll have better performance with GLPK. I don't know.

Szabolcs gravatar imageSzabolcs ( 2019-10-11 13:18:18 -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

1 follower


Asked: 2019-10-11 02:27:37 -0500

Seen: 127 times

Last updated: Oct 21 '19