Bug in edge disjoint spanning trees

[kliem]

Timeout when creating edge disjoint spanning trees:

sage: dig6_string = r'[E_S?_hKIH@eos[BSg???Q@FShGC?hTHUGM?IPug?'
sage: dig6_string += r'JOEYCdOzdkQGo@ADA@AAg?GAQW?'
sage: dig6_string += r'[aIaSwHYcD@qQb@Dd?\hJTI@OHlJ_?C_OEIKoeCR@_BC?Q?'
sage: dig6_string += r'?YBFosqITEA?IvCU_'
sage: G = DiGraph(dig6_string)
sage: G.edge_connectivity(5)
5
sage: G.edge_disjoint_spanning_trees(5)  # timeout

This contradicts a doctest in src/sage/graphs/generic_graph.py.

Depends on #32911

CC: @dcoudert @mkoeppe

Component: graph theory

Keywords: spanning trees

Author: David Coudert

Branch: e23edfc

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/32169

[dcoudert]

comment:2

I get the answer very quickly with cplex and in a few seconds with coin. However, with glpk it takes ages (although it gets quickly the right LP bound).

sage: %time G.edge_disjoint_spanning_trees(5, solver='Cplex')                                                                                      
CPU times: user 2.74 s, sys: 67.5 ms, total: 2.81 s
Wall time: 663 ms
[Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices]
sage: %time G.edge_disjoint_spanning_trees(5, solver='Coin')                                                                                       
CPU times: user 3.52 s, sys: 76.7 ms, total: 3.6 s
Wall time: 3.61 s
[Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices]

Concerning the \h, if I replace it in the string with \\h, then I don't get the warning anymore. Not sure how to fix this issue.

[DaveWitteMorris]

comment:3

Another option for the \h (which I think is better) would be to use raw strings (put an 'r' before each of them, or before the one that is giving an error, at least). As I understand it, dig6 strings can include any visible ascii character, including a backslash.

[kliem]

comment:5

Replying to @DaveWitteMorris:

Another option for the \h (which I think is better) would be to use raw strings (put an 'r' before each of them, or before the one that is giving an error, at least). As I understand it, dig6 strings can include any visible ascii character, including a backslash.

Thanks for the info. So this was a usage error from my side. I fixed the description.

[dcoudert]

comment:6

The current method is based on integer linear programming and is very slow.

For undirected graphs, we can try to implement one of the existing polynomial time algorithm such as the one described in https://doi.org/10.1287/moor.10.4.701. I don't know yet if there is a simpler algorithms.

I don't know the algorithms for directed graphs.

[dcoudert]

Branch: public/graphs/32169_new_ILP

[dcoudert]

comment:7

At first, I propose an alternative ILP formulation based on the Miller-Tucker-Zemlin subtour elimination constraints to replace the current formulation which is based on the maximum average degree. I obtain the solution for the reported digraph with glpk in 1.4s on a macbook air.

sage: d6 = r'[E_S?_hKIH@eos[BSg???Q@FShGC?hTHUGM?IPug?JOEYCdOzdkQGo@ADA@AAg?GAQW?[aIaSwHYcD@qQb@Dd?\hJTI@OHlJ_?C_OEIKoeCR@_BC?Q??YBFosqITEA?IvCU_' 
sage: G = DiGraph(d6)                                                                                                                              
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='Cplex')                                                                                  
CPU times: user 4.83 s, sys: 97.1 ms, total: 4.93 s
Wall time: 825 ms
sage: F                                                                                                                                            
[Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices,
 Digraph on 28 vertices]
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='Coin')                                                                                   
CPU times: user 2.3 s, sys: 65.2 ms, total: 2.37 s
Wall time: 2.38 s
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='GLPK')                                                                                   
CPU times: user 1.36 s, sys: 7.96 ms, total: 1.36 s
Wall time: 1.37 s

Of course, it would be better to implement the polynomial time algorithms.

---

New commits:

76ce723

trac #32169: new ILP formulation

[dcoudert]

Author: David Coudert

[dcoudert]

Commit: 76ce723

[sagetrac-git]

Changed commit from 76ce723 to 047afda

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

047afda

trac #32169: enforce equality in the number of incoming edges

[dcoudert]

comment:9

I get slightly better running time when I force equality for the number of incoming edges.

sage: %time F = G.edge_disjoint_spanning_trees(5, solver='Cplex')                                                                                  
CPU times: user 2.2 s, sys: 84.2 ms, total: 2.28 s
Wall time: 506 ms
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='Coin')                                                                                   
CPU times: user 2.36 s, sys: 53.2 ms, total: 2.41 s
Wall time: 2.44 s
sage: %time F = G.edge_disjoint_spanning_trees(5, solver='GLPK')                                                                                   
CPU times: user 1.22 s, sys: 8.05 ms, total: 1.22 s
Wall time: 1.23 s

However, if I remove the constraint ensuring that each vertex is incident to a selected edge, the program is way slower to solve.

[tscrim]

comment:10

Do you want to keep trying to improve the speed on this ticket or go with this current version and work on further improvements later?

[dcoudert]

comment:11

I prefer to work on further improvements later. I had a look at a paper from Roskind and Tarjan for undirected graphs and it is already quite involved (I don't know if better / simpler algorithms have been proposed since 1985) and I have not seen any proposal for directed graphs yet.

[tscrim]

comment:12

Okay, LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[kliem]

comment:13

With this ticket our claim is still way above that what sage can do. For those three graphs with 12 vertices, this ticket fails:

sage: g1 = DiGraph(r'KAGBiSahR?D?Hw@jFDbLyTWAE')
sage: g2 = DiGraph(r'KW?ACPRIJh_AKPCk_KAORC`Bw') 
sage: g3 = DiGraph(r'KOOB?R?@G_IGc_U}`NEMjE@CE') 

Even worse, it seems to work find on the develop branch. However, on the develop branch I'm getting UnboundedLocalError, because classes are referenced before assignment.

Anyway, while this resolved the one particular case I reported, it seems to have created various other problems.

[kliem]

comment:14

E.g.

g = DiGraph(r'SKwrQo`?DpS?hP@OaOYABAYP`OO[_JekGGPI?O_?bKG?IB?B@[BDGiKBCQMGoTp?GGC_') 

is resolved now, but didn't work before.

[dcoudert]

comment:15

Can you be more specific on the errors you get ? I can try to improve the formulation, and with more time to implement the polynomial time algorithms.

[dcoudert]

Changed commit from 8d42f68 to e23edfc

[dcoudert]

Changed branch from public/graphs/32169_new_ILP_v2 to public/graphs/32169_v3

[dcoudert]

comment:40

FYI: thanks to the Loukas Georgiadis and his co-authors (see #comment:37), I now have a working implementation of the algorithm of Gabow for computing the edge connectivity of a digraph. They gave me a pure C code that I turned into an easier to read Cython code. It still lacks comments and doctests...

I'm still working on the second part of the paper of Gabow for extracting the k-edge-disjoint spanning trees (not obvious). I will not push code before it's done as I may have to refactor some parts of the first algorithm that are also used in the second part.

[tscrim]

comment:41

No problem. Just let me know when you're ready for a review.

[dcoudert]

comment:44

Replying to @dcoudert:

FYI: thanks to the Loukas Georgiadis and his co-authors (see #comment:37), I now have a working implementation of the algorithm of Gabow for computing the edge connectivity of a digraph. They gave me a pure C code that I turned into an easier to read Cython code. It still lacks comments and doctests...

This is now #33839.

[tscrim]

comment:45

Then positive review.

[vbraun]

Changed branch from public/graphs/32169_v3 to e23edfc

[antonio-rojas]

comment:47

This makes the test suite hang with certain random seeds:

sage -t --long --random-seed=226966935809951887489348852629671397336 /usr/lib/python3.10/site-packages/sage/graphs/generic_graph.py
    Timed out
**********************************************************************
Tests run before process (pid=581821) timed out:
[...]
sage: trees = g.edge_disjoint_spanning_trees(k, algorithm="MILP") ## line 6579 ##
------------------------------------------------------------------------
/usr/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0x76fd)[0x7fdff2caa6fd]
/usr/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0x77bc)[0x7fdff2caa7bc]
/usr/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0xa4e2)[0x7fdff2cad4e2]
/usr/lib/libc.so.6(+0x3e8e0)[0x7fdff42788e0]
/usr/lib/libglpk.so.40(glp_get_mat_col+0x4b)[0x7fdf7d591dfb]
/usr/lib/libglpk.so.40(glp_eval_tab_row+0x198)[0x7fdf7d5b3328]
/usr/lib/libglpk.so.40(+0x43ed5)[0x7fdf7d5b7ed5]
/usr/lib/libglpk.so.40(+0x49950)[0x7fdf7d5bd950]
/usr/lib/libglpk.so.40(+0x3be63)[0x7fdf7d5afe63]
/usr/lib/libglpk.so.40(glp_intopt+0xd2c)[0x7fdf7d5b108c]
/usr/lib/python3.10/site-packages/sage/numerical/backends/glpk_backend.cpython-310-x86_64-linux-gnu.so(+0x1f618)[0x7fdf7d6be618]
/usr/lib/python3.10/site-packages/sage/numerical/mip.cpython-310-x86_64-linux-gnu.so(+0x2bc83)[0x7fdf84e5ac83]
/usr/lib/libpython3.10.so.1.0(+0x154be1)[0x7fdff459bbe1]
/usr/lib/libpython3.10.so.1.0(_PyObject_MakeTpCall+0x2ab)[0x7fdff45954bb]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x5aaf)[0x7fdff4590b9f]
/usr/lib/libpython3.10.so.1.0(+0x1603f6)[0x7fdff45a73f6]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x149a)[0x7fdff458c58a]
/usr/lib/libpython3.10.so.1.0(+0x143080)[0x7fdff458a080]
/usr/lib/libpython3.10.so.1.0(PyEval_EvalCode+0x94)[0x7fdff463cbb4]
/usr/lib/libpython3.10.so.1.0(+0x1fb9cb)[0x7fdff46429cb]
/usr/lib/libpython3.10.so.1.0(+0x15528f)[0x7fdff459c28f]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x346)[0x7fdff458b436]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyObject_FastCallDictTstate+0xdb)[0x7fdff45947ab]
/usr/lib/libpython3.10.so.1.0(_PyObject_Call_Prepend+0x6d)[0x7fdff45a4c5d]
/usr/lib/libpython3.10.so.1.0(+0x22d462)[0x7fdff4674462]
/usr/lib/libpython3.10.so.1.0(_PyObject_MakeTpCall+0x2ab)[0x7fdff45954bb]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x5164)[0x7fdff4590254]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(+0x1603f6)[0x7fdff45a73f6]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x149a)[0x7fdff458c58a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyObject_FastCallDictTstate+0xdb)[0x7fdff45947ab]
/usr/lib/libpython3.10.so.1.0(+0x15d08d)[0x7fdff45a408d]
/usr/lib/libpython3.10.so.1.0(_PyObject_MakeTpCall+0x283)[0x7fdff4595493]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x5164)[0x7fdff4590254]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x4ebf)[0x7fdff458ffaf]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x4ebf)[0x7fdff458ffaf]
/usr/lib/libpython3.10.so.1.0(+0x1603f6)[0x7fdff45a73f6]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x4ebf)[0x7fdff458ffaf]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(_PyFunction_Vectorcall+0x79)[0x7fdff459c099]
/usr/lib/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x77a)[0x7fdff458b86a]
/usr/lib/libpython3.10.so.1.0(+0x143080)[0x7fdff458a080]
/usr/lib/libpython3.10.so.1.0(PyEval_EvalCode+0x94)[0x7fdff463cbb4]
/usr/lib/libpython3.10.so.1.0(+0x205103)[0x7fdff464c103]
/usr/lib/libpython3.10.so.1.0(+0x200a9a)[0x7fdff4647a9a]
/usr/lib/libpython3.10.so.1.0(+0xa183c)[0x7fdff44e883c]
/usr/lib/libpython3.10.so.1.0(_PyRun_SimpleFileObject+0x3cc)[0x7fdff44e84ed]
/usr/lib/libpython3.10.so.1.0(_PyRun_AnyFileObject+0x89)[0x7fdff44e8ea0]
/usr/lib/libpython3.10.so.1.0(Py_RunMain+0x3dd)[0x7fdff46586fd]
/usr/lib/libpython3.10.so.1.0(Py_BytesMain+0x3b)[0x7fdff462e19b]
/usr/lib/libc.so.6(+0x29290)[0x7fdff4263290]
/usr/lib/libc.so.6(__libc_start_main+0x8a)[0x7fdff426334a]
/usr/bin/python(_start+0x25)[0x5642f4693045]
------------------------------------------------------------------------

[antonio-rojas]

Changed commit from e23edfc to none

[dcoudert]

comment:48

outch :(

This is for

g = Graph(']sLa{AZZs?fCoOOPAqJaO_byp|e?w[U@cObCktCSsAO]b{cndeJIT`G~dcaXWEBwUk_kLar@sg')

It's a too hard instance for this formulation with GLPK.

I see 2 solutions here: use a much smaller instance (10 nodes ?) or deprecate the ILP formulation. We have the polynomial time Roskind-Tarjan algorithm for undirected graphs and we should soon have an algorithm for directed graphs (GSoC project).

[tscrim]

comment:49

I would make the number of nodes for the test smaller as it is less invasive of a fix.

[dcoudert]

comment:50

I opened #33884.

[dimpase]

comment:51

This bug has roared its ugly head again. Observed on Gentoo x86_64 Linux, Sage 9.8.beta7, with system-installed glpk-5.0-r1. What's even more disturbing is that doing G.edge_disjoint_spanning_trees(5,solver='ppl') does not seem to terminate either.

[dimpase]

comment:52

and after I installed Coin (used one from the system, coinor-cbc-2.10.5), I get
a multithreading-related crash:

....: sage: G.edge_connectivity()
python3: CbcModel.cpp:16173: int CbcModel::doOneNode(CbcModel*, CbcNode*&, CbcNode*&): Assertion `masterThread_' failed.
------------------------------------------------------------------------
/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0x7dfb)[0x7f4f7b4f6dfb]
/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0x7ea8)[0x7f4f7b4f6ea8]
/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/cysignals/signals.cpython-310-x86_64-linux-gnu.so(+0xa1ed)[0x7f4f7b4f91ed]
/lib64/libc.so.6(+0x37950)[0x7f4f89103950]
/lib64/libc.so.6(+0x8342c)[0x7f4f8914f42c]
/lib64/libc.so.6(gsignal+0x12)[0x7f4f891038b2]
/lib64/libc.so.6(abort+0xd7)[0x7f4f890ee471]
/lib64/libc.so.6(+0x22395)[0x7f4f890ee395]
/lib64/libc.so.6(+0x30b92)[0x7f4f890fcb92]
/usr/lib64/libCbc.so.3(_ZN8CbcModel9doOneNodeEPS_RP7CbcNodeS3_+0x3055)[0x7f4e253859f5]
/usr/lib64/libCbc.so.3(_ZN8CbcModel14branchAndBoundEi+0x320c)[0x7f4e25388e5c]
/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage_numerical_backends_coin/coin_backend.cpython-310-x86_64-linux-gnu.so(+0x21c05)[0x7f4e2540cc05]
/mnt/opt/Sage/sage-dev/src/sage/numerical/mip.cpython-310-x86_64-linux-gnu.so(+0x1a30f)[0x7f4e2a14a30f]
/usr/lib64/libpython3.10.so.1.0(+0x110fa3)[0x7f4f893abfa3]
/mnt/opt/Sage/sage-dev/src/sage/graphs/connectivity.cpython-310-x86_64-linux-gnu.so(+0x1012f)[0x7f4e2ad2112f]
/mnt/opt/Sage/sage-dev/src/sage/graphs/connectivity.cpython-310-x86_64-linux-gnu.so(+0x40cff)[0x7f4e2ad51cff]
/mnt/opt/Sage/sage-dev/src/sage/graphs/connectivity.cpython-310-x86_64-linux-gnu.so(+0x4622f)[0x7f4e2ad5722f]
/usr/lib64/libpython3.10.so.1.0(_PyObject_MakeTpCall+0x90)[0x7f4f89362180]
/usr/lib64/libpython3.10.so.1.0(+0xc9db2)[0x7f4f89364db2]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0xa11f)[0x7f4f8930a68f]
/usr/lib64/libpython3.10.so.1.0(PyEval_EvalCode+0xcd)[0x7f4f8945c20d]
/usr/lib64/libpython3.10.so.1.0(+0x1ba021)[0x7f4f89455021]
/usr/lib64/libpython3.10.so.1.0(+0x111738)[0x7f4f893ac738]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x75b2)[0x7f4f89307b22]
/usr/lib64/libpython3.10.so.1.0(+0xdc82b)[0x7f4f8937782b]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x9829)[0x7f4f89309d99]
/usr/lib64/libpython3.10.so.1.0(+0xdc82b)[0x7f4f8937782b]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x9829)[0x7f4f89309d99]
/usr/lib64/libpython3.10.so.1.0(+0xdd53b)[0x7f4f8937853b]
/usr/lib64/libpython3.10.so.1.0(+0xd1208)[0x7f4f8936c208]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7a6c)[0x7f4f89307fdc]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x75b2)[0x7f4f89307b22]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7a6c)[0x7f4f89307fdc]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(+0xc9d78)[0x7f4f89364d78]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7645)[0x7f4f89307bb5]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7a6c)[0x7f4f89307fdc]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7a6c)[0x7f4f89307fdc]
/usr/lib64/libpython3.10.so.1.0(+0x1c1380)[0x7f4f8945c380]
/usr/lib64/libpython3.10.so.1.0(_PyEval_EvalFrameDefault+0x7a6c)[0x7f4f89307fdc]
/usr/lib64/libpython3.10.so.1.0(PyEval_EvalCode+0xcd)[0x7f4f8945c20d]
/usr/lib64/libpython3.10.so.1.0(+0x2071e9)[0x7f4f894a21e9]
/usr/lib64/libpython3.10.so.1.0(_PyRun_SimpleFileObject+0x164)[0x7f4f894a33e4]
/usr/lib64/libpython3.10.so.1.0(_PyRun_AnyFileObject+0x3c)[0x7f4f894a3a3c]
/usr/lib64/libpython3.10.so.1.0(Py_RunMain+0x7e8)[0x7f4f894c3fd8]
/usr/lib64/libpython3.10.so.1.0(Py_BytesMain+0x5a)[0x7f4f894c458a]
/lib64/libc.so.6(+0x2334a)[0x7f4f890ef34a]
/lib64/libc.so.6(__libc_start_main+0x7c)[0x7f4f890ef3fc]
python3(_start+0x21)[0x55de6f9c7081]
------------------------------------------------------------------------
Attaching gdb to process id 8887.
^CTraceback (most recent call last):
  File "/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/bin/cysignals-CSI", line 225, in <module>
    main(args)
  File "/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/bin/cysignals-CSI", line 174, in main
    trace = run_gdb(args.pid, not args.nocolor)
  File "/mnt/opt/Sage/sage-dev/local/var/lib/sage/venv-python3.10/bin/cysignals-CSI", line 98, in run_gdb
    stdout, stderr = cmd.communicate(gdb_commands(pid, color))
  File "/usr/lib/python3.10/subprocess.py", line 1154, in communicate
    stdout, stderr = self._communicate(input, endtime, timeout)
  File "/usr/lib/python3.10/subprocess.py", line 2005, in _communicate
    ready = selector.select(timeout)
  File "/usr/lib/python3.10/selectors.py", line 416, in select
    fd_event_list = self._selector.poll(timeout)
KeyboardInterrupt

[dimpase]

comment:53

With Sage's supplied cbc, it works, including G.edge_disjoint_spanning_trees(5,solver='Coin')

[mkoeppe]

comment:54

It's a known problem that sage_numerical_backends_coin does not work properly with newer, distribution-provided COIN installations; see #30644

[mkoeppe]

comment:55

The way forward with COIN is via CVXpy as middleware - #34251 (needs review)

[dcoudert]

comment:56

Unfortunately I'm currently too busy to work on the implementation of the combinatorial algorithm of Gabow but it's in my plan for the next months. It's a long and complex algorithm.