Lot of broken doctests with Coin

[edd8e884-f507-429a-b577-5d554626c0fe]

With cbc installed on 9.6, and Coin as the default solver:

sage: default_mip_solver()
'Coin'

there are a lot of broken doctests involving MixedIntegerLinearProgram, showing wrong (at least unexpected) results:

sagemath@debian:/opt/sagemath/sage-9.6$ ./sage -t --long --random-seed=220977816658885637174790555079465548143 src/sage/combinat/designs/incidence_structures.py  # 1 doctest failed
Running doctests with ID 2022-05-28-15-18-04-1d37358f.
Git branch: develop
Using --optional=4ti2,barvinok,benzene,bliss,buckygen,ccache,coxeter3,cryptominisat,csdp,cunningham_tables,cylp,d3js,debian,debugpy,dot2tex,e_antic,fricas,frobby,gap_jupyter,gap_packages,glucose,igraph,info,jupymake,kenzo,latte_int,libogg,libsemigroups,lidia,mathics,mathics_scanner,mcqd,meataxe,mpfrcx,normaliz,notedown,palettable,pandoc_attributes,pari_elldata,pari_galpol,pari_jupyter,pari_nftables,pari_seadata,pint,pip,plantri,polylib,polymake,pycosat,pycryptosat,pynormaliz,pysingular,python_igraph,rst2ipynb,rubiks,saclib,sage,sage_numerical_backends_coin,sage_spkg,singular_jupyter,sip,sirocco,symengine,symengine_py,tdlib,texttable,tides,topcom
Features to be detected: 4ti2,benzene,bliss,buckygen,conway_polynomials,csdp,database_cremona_ellcurve,database_cremona_mini_ellcurve,database_jones_numfield,database_knotinfo,dvipng,gfan,graphviz,imagemagick,jupymake,kenzo,latte_int,lrslib,mcqd,meataxe,nauty,palp,pandoc,pdf2svg,pdftocairo,phitigra,plantri,polytopes_db,polytopes_db_4d,pynormaliz,python_igraph,rubiks,sage.combinat,sage.geometry.polyhedron,sage.graphs,sage.groups,sage.plot,sage.rings.number_field,sage.rings.padics,sage.rings.real_double,sage.symbolic,sage_numerical_backends_coin,sagemath_doc_html,sphinx,tdlib
Doctesting 1 file.
sage -t --long --warn-long 60.1 --random-seed=220977816658885637174790555079465548143 src/sage/combinat/designs/incidence_structures.py
**********************************************************************
File "src/sage/combinat/designs/incidence_structures.py", line 2041, in sage.combinat.designs.incidence_structures.IncidenceStructure.?
Failed example:
    len(designs.steiner_triple_system(7).coloring())
Expected:
    3
Got:
    2
**********************************************************************
1 item had failures:
   1 of  35 in sage.combinat.designs.incidence_structures.IncidenceStructure.?
    [346 tests, 1 failure, 1.64 s]
----------------------------------------------------------------------
sage -t --long --warn-long 60.1 --random-seed=220977816658885637174790555079465548143 src/sage/combinat/designs/incidence_structures.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 1.9 seconds
    cpu time: 1.7 seconds
    cumulative wall time: 1.6 seconds
Features detected for doctesting: 

sagemath@debian:/opt/sagemath/sage-9.6$ ./sage -t --long --random-seed=220977816658885637174790555079465548143 src/sage/graphs/generic_graph.py
Running doctests with ID 2022-05-28-15-22-06-18843e15.
Git branch: develop
Using --optional=4ti2,barvinok,benzene,bliss,buckygen,ccache,coxeter3,cryptominisat,csdp,cunningham_tables,cylp,d3js,debian,debugpy,dot2tex,e_antic,fricas,frobby,gap_jupyter,gap_packages,glucose,igraph,info,jupymake,kenzo,latte_int,libogg,libsemigroups,lidia,mathics,mathics_scanner,mcqd,meataxe,mpfrcx,normaliz,notedown,palettable,pandoc_attributes,pari_elldata,pari_galpol,pari_jupyter,pari_nftables,pari_seadata,pint,pip,plantri,polylib,polymake,pycosat,pycryptosat,pynormaliz,pysingular,python_igraph,rst2ipynb,rubiks,saclib,sage,sage_numerical_backends_coin,sage_spkg,singular_jupyter,sip,sirocco,symengine,symengine_py,tdlib,texttable,tides,topcom
Features to be detected: 4ti2,benzene,bliss,buckygen,conway_polynomials,csdp,database_cremona_ellcurve,database_cremona_mini_ellcurve,database_jones_numfield,database_knotinfo,dvipng,gfan,graphviz,imagemagick,jupymake,kenzo,latte_int,lrslib,mcqd,meataxe,nauty,palp,pandoc,pdf2svg,pdftocairo,phitigra,plantri,polytopes_db,polytopes_db_4d,pynormaliz,python_igraph,rubiks,sage.combinat,sage.geometry.polyhedron,sage.graphs,sage.groups,sage.plot,sage.rings.number_field,sage.rings.padics,sage.rings.real_double,sage.symbolic,sage_numerical_backends_coin,sagemath_doc_html,sphinx,tdlib
Doctesting 1 file.
sage -t --long --warn-long 60.1 --random-seed=220977816658885637174790555079465548143 src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 9216, in sage.graphs.generic_graph.GenericGraph.nowhere_zero_flow
Failed example:
    h = g.nowhere_zero_flow(k=3)
Expected:
    Traceback (most recent call last):
    ...
    EmptySetError: the problem has no feasible solution
Got:
    <BLANKLINE>
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 9841, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    p1,p2 = g.disjoint_routed_paths([((0, 0), (4, 4)), ((0, 4), (4, 0))])
Expected:
    Traceback (most recent call last):
    ...
    EmptySetError: the disjoint routed paths do not exist
Got:
    <BLANKLINE>
**********************************************************************
2 items had failures:
   1 of 1148 in sage.graphs.generic_graph.GenericGraph.?
   1 of  29 in sage.graphs.generic_graph.GenericGraph.nowhere_zero_flow
    [3777 tests, 2 failures, 51.15 s]
----------------------------------------------------------------------
sage -t --long --warn-long 60.1 --random-seed=220977816658885637174790555079465548143 src/sage/graphs/generic_graph.py  # 2 doctests failed
----------------------------------------------------------------------
Total time for all tests: 57.0 seconds
    cpu time: 38.4 seconds
    cumulative wall time: 51.2 seconds
Features detected for doctesting: graphviz,sage.groups,sage.symbolic

sagemath@debian:/opt/sagemath/sage-9.6$ ./sage -t --long --random-seed=220977816658885637174790555079465548143 src/sage/graphs/graph.py  # 3 doctests failed
Running doctests with ID 2022-05-28-15-23-41-36115fcf.
Git branch: develop
Using --optional=4ti2,barvinok,benzene,bliss,buckygen,ccache,coxeter3,cryptominisat,csdp,cunningham_tables,cylp,d3js,debian,debugpy,dot2tex,e_antic,fricas,frobby,gap_jupyter,gap_packages,glucose,igraph,info,jupymake,kenzo,latte_int,libogg,libsemigroups,lidia,mathics,mathics_scanner,mcqd,meataxe,mpfrcx,normaliz,notedown,palettable,pandoc_attributes,pari_elldata,pari_galpol,pari_jupyter,pari_nftables,pari_seadata,pint,pip,plantri,polylib,polymake,pycosat,pycryptosat,pynormaliz,pysingular,python_igraph,rst2ipynb,rubiks,saclib,sage,sage_numerical_backends_coin,sage_spkg,singular_jupyter,sip,sirocco,symengine,symengine_py,tdlib,texttable,tides,topcom
Features to be detected: 4ti2,benzene,bliss,buckygen,conway_polynomials,csdp,database_cremona_ellcurve,database_cremona_mini_ellcurve,database_jones_numfield,database_knotinfo,dvipng,gfan,graphviz,imagemagick,jupymake,kenzo,latte_int,lrslib,mcqd,meataxe,nauty,palp,pandoc,pdf2svg,pdftocairo,phitigra,plantri,polytopes_db,polytopes_db_4d,pynormaliz,python_igraph,rubiks,sage.combinat,sage.geometry.polyhedron,sage.graphs,sage.groups,sage.plot,sage.rings.number_field,sage.rings.padics,sage.rings.real_double,sage.symbolic,sage_numerical_backends_coin,sagemath_doc_html,sphinx,tdlib
Doctesting 1 file.
sage -t --long --warn-long 60.1 --random-seed=220977816658885637174790555079465548143 src/sage/graphs/graph.py
**********************************************************************
File "src/sage/graphs/graph.py", line 4283, in sage.graphs.graph.Graph.?
Failed example:
    g.has_homomorphism_to(graphs.CycleGraph(4)) is not False
Expected:
    False
Got:
    True
**********************************************************************
File "src/sage/graphs/graph.py", line 4690, in sage.graphs.graph.Graph.minor
Failed example:
    L = g.minor(graphs.CompleteGraph(3))
Expected:
    Traceback (most recent call last):
    ...
    ValueError: This graph has no minor isomorphic to H !
Got:
    <BLANKLINE>
**********************************************************************
File "src/sage/graphs/graph.py", line 5918, in sage.graphs.graph.Graph.?
Failed example:
    g.topological_minor(graphs.CycleGraph(3))
Expected:
    False
Got:
    Subgraph of (Subgraph of (RandomGNP(15,0.300000000000000))): Graph on 0 vertices
**********************************************************************
2 items had failures:
   2 of 334 in sage.graphs.graph.Graph.?
   1 of  14 in sage.graphs.graph.Graph.minor
    [1262 tests, 3 failures, 26.68 s]
----------------------------------------------------------------------
sage -t --long --warn-long 60.1 --random-seed=220977816658885637174790555079465548143 src/sage/graphs/graph.py  # 3 doctests failed
----------------------------------------------------------------------
Total time for all tests: 27.0 seconds
    cpu time: 30.4 seconds
    cumulative wall time: 26.7 seconds
Features detected for doctesting: sage.groups,sage.symbolic

Depends on #34251

CC: @dimpase

Component: packages: optional

Keywords: sdl

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

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:1

Note that this was built on a Core2 Duo CPU (the goal is to have SDL run on old machines with fewer CPU flags).

[mkoeppe]

comment:2

dup of #30635, I guess

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:3

Replying to @mkoeppe:

dup of #30635, I guess

Indeed, perhaps should both tickets be merged (the current ticket shows a different set of errors).

Should i understand that Coin is not the culprit, and that the other mip solvers may give the same amount of wrong results due to numerical noise ? It is important for me to know, because i might just remove cbc from the next SDL (to exchange speed for correctness).

[mkoeppe]

comment:4

There were multiple things wrong. Meta-ticket #32191 has a large number tickets that fixed how various Sage code was using the numerical results from solvers.

In addition, it appears that sage-numerical-backend-coin is not compatible with the CBC 2.10 series. I haven't had the time to look into this issue.

As the way forward I want to use #31962, which makes sage-numerical-backend-coin obsolete.

[mkoeppe]

comment:5

In the meantime, you can use --without-system-cbc. Our spkg is still using CBC 2.9.x, as the update ticket #30644 has stalled

[mkoeppe]

Dependencies: #34251

[mkoeppe]

comment:6

34251 solves this, needs review

[dcoudert]

Since the issue is fixed, I set this issue to positive review.