doctests failures in sage/graphs when using COIN solver #30635

seblabbe · 2020-09-22T20:40:13Z

On Ubuntu 18.04, with 9.2.beta13, running

sage -tp src/sage/graphs/generic_graph.py src/sage/graphs/graph.py

with the following optional packages:

Using --optional=4ti2,build,ccache,cryptominisat,dochtml,dot2tex,e_antic,fricas,glucose,latte_int,libnauty,lidia,lrslib,memlimit,normaliz,notedown,openssl,pandoc_attributes,pycosat,pynormaliz,rst2ipynb,sage,sage_numerical_backends_coin

gives

sage -t --random-seed=0 src/sage/graphs/graph.py
**********************************************************************
File "src/sage/graphs/graph.py", line 4507, in sage.graphs.graph.Graph.has_homomorphism_to
Failed example:
    g.has_homomorphism_to(graphs.CycleGraph(4)) is not False
Expected:
    False
Got:
    True
**********************************************************************
File "src/sage/graphs/graph.py", line 4902, 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 6112, in sage.graphs.graph.Graph.topological_minor
Failed example:
    g.topological_minor(graphs.CycleGraph(3))
Expected:
    False
Got:
    Subgraph of (Subgraph of (RandomGNP(15,0.300000000000000))): Graph on 0 vertices
**********************************************************************
3 items had failures:
   1 of  10 in sage.graphs.graph.Graph.has_homomorphism_to
   1 of  12 in sage.graphs.graph.Graph.minor
   1 of   7 in sage.graphs.graph.Graph.topological_minor
    [1229 tests, 3 failures, 12.35 s]
sage -t --random-seed=0 src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 8909, 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 9530, in sage.graphs.generic_graph.GenericGraph.disjoint_routed_paths
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   5 in sage.graphs.generic_graph.GenericGraph.disjoint_routed_paths
   1 of  29 in sage.graphs.generic_graph.GenericGraph.nowhere_zero_flow
    [3458 tests, 2 failures, 13.67 s]
----------------------------------------------------------------------
sage -t --random-seed=0 src/sage/graphs/graph.py  # 3 doctests failed
sage -t --random-seed=0 src/sage/graphs/generic_graph.py  # 2 doctests failed
----------------------------------------------------------------------

Seems to be related to cbc/coin. Here are the involved versions:

$ sage -optional | grep coin
sage_numerical_backends_coin............9.0b12 (9.0b12)
$ sage -optional | grep cbc
cbc.....................................2.9.4.p0 (not_installed)
$ cbc --version
Welcome to the CBC MILP Solver 
Version: 2.9.9 
Build Date: Aug 21 2017

Depends on #30644

CC: @mkoeppe @dimpase

Component: graph theory

Reviewer: David Coudert

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

The text was updated successfully, but these errors were encountered:

dcoudert · 2020-09-22T21:23:16Z

comment:1

I suspect it is due to coin. Can you try for instance

sage: g = graphs.CycleGraph(9)
sage: g.has_homomorphism_to(graphs.CycleGraph(4), solver='GLPK')
False

fedora 32, with cplex as default solver, I get

musclotte:/home/dcoudert/sage> ./sage -version
SageMath version 9.2.beta13, Release Date: 2020-09-21
musclotte:/home/dcoudert/sage> ./sage -tp src/sage/graphs/generic_graph.py src/sage/graphs/graph.py 
too few successful tests, not using stored timings
Running doctests with ID 2020-09-22-23-04-40-6379f74f.
Git branch: develop
Using --optional=benzene,bliss,buckygen,build,cryptominisat,csdp,dochtml,dot2tex,gap_packages,glucose,igraph,libsemigroups,mcqd,memlimit,plantri,python_igraph,rubiks,sage,sage_numerical_backends_cplex,sage_numerical_backends_gurobi,tdlib
Doctesting 2 files using 8 threads.
sage -t --random-seed=0 src/sage/graphs/graph.py
    [1244 tests, 21.04 s]
sage -t --random-seed=0 src/sage/graphs/generic_graph.py
    [3514 tests, 47.27 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 48.2 seconds
    cpu time: 122.6 seconds
    cumulative wall time: 68.3 seconds

same on macOS 10.15.6 but with only cplex as optional package.

seblabbe · 2020-09-23T08:52:44Z

comment:2

Ok, I see, I need to reinstall Gurobi and/or CPLEX again, but I haven't needed it recently.

I get this:

sage: g = graphs.CycleGraph(9) 
sage: g.has_homomorphism_to(graphs.CycleGraph(4))                     
{1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 1}
sage: g.has_homomorphism_to(graphs.CycleGraph(4), solver='COIN')                     
{1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 1}
sage: g.has_homomorphism_to(graphs.CycleGraph(4), solver='GLPK')                     
Long-step dual simplex will be used
False

dcoudert · 2020-09-23T09:02:08Z

comment:3

So something is wrong with cbc/coin. I never use it...

FYI, the Long-step dual simplex will be used message when using glpk is ignored in doctests since #29587.

seblabbe · 2020-09-23T09:03:25Z

comment:4

What is weird is that vertices 0 and 8 are not a key of the dictionnary "found" by coin:

sage: g8 = graphs.CycleGraph(8)                                                            
sage: g9 = graphs.CycleGraph(9)                                                            
sage: g4 = graphs.CycleGraph(4)                                                            
sage: g9.has_homomorphism_to(g4, solver='COIN') # key 0 and 8 are missing in the output
{1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 1}
sage: g8.has_homomorphism_to(g4, solver='COIN')                                            
{0: 0, 1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 1}
sage: g9.has_homomorphism_to(g4, solver='GLPK')                                            
Long-step dual simplex will be used
False
sage: g8.has_homomorphism_to(g4, solver='GLPK')                                            
Long-step dual simplex will be used
{0: 0, 1: 3, 2: 0, 3: 3, 4: 0, 5: 3, 6: 0, 7: 3}

seblabbe · 2020-09-23T09:08:49Z

comment:6

Do you think #30637 is also cbc/coin related?

dcoudert · 2020-09-23T09:22:31Z

comment:8

Replying to @seblabbe:

Do you think #30637 is also cbc/coin related?

not sure. See #29551

seblabbe · 2020-09-23T09:23:51Z

comment:9

What is the difference between cbc and coin?

Can I use solver='COIN' if cbc is not installed?

$ sage -optional | grep cbc
cbc.....................................2.9.4.p0 (not_installed)

seblabbe · 2020-09-23T09:28:09Z

comment:10

I confirm that the issue dissappear after installing cbc:

$ sage -optional | grep cbc
cbc.....................................2.9.4.p0 (2.9.4.p0)

sage -t --random-seed=0 src/sage/graphs/generic_graph.py
    [3458 tests, 13.66 s]
sage -t --random-seed=0 src/sage/graphs/graph.py
    [1229 tests, 14.46 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------

seblabbe · 2020-09-23T09:33:40Z

comment:11

Something is weird in the configuration, because I did --enable-cbc:

$ head config.log
This file contains any messages produced by compilers while
running configure, to aid debugging if configure makes a mistake.

It was created by Sage configure 9.2.beta13, which was
generated by GNU Autoconf 2.69.  Invocation command line was

  $ ./configure --enable-experimental-packages --enable-download-from-upstream-url --enable-ccache --enable-dot2tex --enable-rst2ipynb --enable-openssl --enable-cbc --enable-cryptominisat --enable-pycosat --enable-glucose --enable-sage_numerical_backends_coin --enable-pynormaliz --enable-latte_int --enable-awali --enable-fricas --no-create --no-recursion

## --------- ##
## Platform. ##

So, I should not need to run sage -i cbc after...

dcoudert · 2020-09-23T09:37:46Z

comment:12

I'm not completely sure of what coin provides apart from a linear programming solver. If I'm right, cbc is the branch and cut / branch and bound engine.

If installing cbc is sufficient to fix the issues, it confirms that we must clarify when we can use coin and when we must use cbc, or if cbc is always needed to with coin.

Concerning configuration / installation, I suggest to ask Dima or Matthias.

seblabbe · 2020-09-23T09:49:49Z

comment:13

adding Matthias in cc here. Questions are:

is it normal to have sage_numerical_backends_coin installed but not cbc (this is the source of the bug in this ticket)?
is it normal that --enable-cbc in the configuration did not installed cbc ?

mkoeppe · 2020-09-23T12:32:56Z

comment:14

sage_numerical_backends_coin does have cbc in its list of dependencies. Normal installs either using the ./configure option --enable-sage_numerical_backends_coin or sage -i sage_numerical_backends_coin should install cbc too.

Note, however, that cbc knows how to find system packages. So --enable-cbc does not install its own copy of cbc if you have one in the system.

seblabbe · 2020-09-23T12:58:23Z

comment:15

ok, I see, and I have

$ cbc --version
Welcome to the CBC MILP Solver 
Version: 2.9.9 
Build Date: Aug 21 2017

installed on the system as opposed to 2.9.4.p0 available in sage. Therefore it seems to be a regression in cbc that happen between 2.9.4.p0 and 2.9.9.

seblabbe · 2020-09-23T13:02:52Z

comment:16

and the latest release version of Cbc is 2.10.5

seblabbe · 2020-09-23T13:07:30Z

comment:17

Should

$ sage -optional | grep cbc
cbc.....................................2.9.4.p0 (not_installed)

instead return

$ sage -optional | grep cbc
cbc.....................................2.9.4.p0 (2.9.9)

if cbc 2.9.9 was found on the system by the --enable-cbc?

mkoeppe · 2020-09-23T13:14:41Z

comment:19

Replying to @seblabbe:

Should

$ sage -optional | grep cbc
cbc.....................................2.9.4.p0 (not_installed)

instead return

$ sage -optional | grep cbc
cbc.....................................2.9.4.p0 (2.9.9)

if cbc 2.9.9 was found on the system by the --enable-cbc?

Best to ignore sage -optional and everything that comes from sage.misc.package...

mkoeppe · 2020-09-23T13:19:23Z

comment:20

Replying to @seblabbe:

What is weird is that vertices 0 and 8 are not a key of the dictionnary "found" by coin:

sage: g8 = graphs.CycleGraph(8)                                                            
sage: g9 = graphs.CycleGraph(9)                                                            
sage: g4 = graphs.CycleGraph(4)                                                            
sage: g9.has_homomorphism_to(g4, solver='COIN') # key 0 and 8 are missing in the output
{1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 1}
sage: g8.has_homomorphism_to(g4, solver='COIN')                                            
{0: 0, 1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 1}
sage: g9.has_homomorphism_to(g4, solver='GLPK')                                            
Long-step dual simplex will be used
False
sage: g8.has_homomorphism_to(g4, solver='GLPK')                                            
Long-step dual simplex will be used
{0: 0, 1: 3, 2: 0, 3: 3, 4: 0, 5: 3, 6: 0, 7: 3}

This seems to come from this code in vertex_cover:

                b = p.get_values(b)
                cover_g = set(v for v in g if b[v] == 1)

which ignores the fact that a numerical solver is used and therefore b will include numerical noise.

seblabbe · 2020-09-23T13:51:15Z

comment:21

Testing with cbc 2.10.5 (upgrade at #30644), the doctest failure stays.

dcoudert · 2020-09-23T14:39:58Z

comment:22

Replying to @mkoeppe:

This seems to come from this code in vertex_cover:
                b = p.get_values(b)
                cover_g = set(v for v in g if b[v] == 1)
which ignores the fact that a numerical solver is used and therefore b will include numerical noise.

well, has_homomorphism_to does not use vertex_cover, but I agree that it might be better to check e.g. if b[v] >= .5. Such tests are not unified (at least) in the graph module.

dcoudert · 2020-09-23T14:41:52Z

comment:23

Replying to @seblabbe:

Testing with cbc 2.10.5 (upgrade at #30644), the doctest failure stays.

I have cbc 2.10.5 installed with hombrew, and after sage -I sage_numerical_backends_coin I get the correct result.

sage: g = graphs.CycleGraph(9)                                                                                                      
sage: g.has_homomorphism_to(graphs.CycleGraph(4), solver='Coin')                                                                    
False

mkoeppe · 2020-09-23T17:03:17Z

comment:24

Replying to @dcoudert:

Replying to @mkoeppe:
This seems to come from this code in vertex_cover:
                b = p.get_values(b)
                cover_g = set(v for v in g if b[v] == 1)
which ignores the fact that a numerical solver is used and therefore b will include numerical noise.
well, has_homomorphism_to does not use vertex_cover,

OK, has_homomorphism_to also has code like this:

            p.solve(log = verbose)
            b = p.get_values(b)
            mapping = dict(x[0] for x in b.items() if x[1])

but I agree that it might be better to check e.g. if b[v] >= .5. Such tests are not unified (at least) in the graph module.

In deed, "at least"... this is severely broken code when solver is a numerical solver.

dcoudert · 2020-09-23T17:36:51Z

comment:25

If I'm correct, there is a confusion in the graph module between coin and cbc. Most of the models should be solved with ILP solvers, so cbc in this case and not coin, right ?

mkoeppe · 2020-09-23T17:42:07Z

comment:26

Replying to @dcoudert:

If I'm correct, there is a confusion in the graph module between coin and cbc. Most of the models should be solved with ILP solvers, so cbc in this case and not coin, right ?

Sage only has one solver backend from the COIN-OR project, and that is the CBC solver, which we use both for mixed integer linear programming and linear programming. The string "coin" designates the use of this backend -- see sage.numerical.backends.generic_backend.get_solver.

chc is the name of the SPKG providing the solver. Sage does not use it directly but only via the SPKG sage_numerical_backends_coin, which provides the class sage_numerical_backends_coin.coin_backend.CoinBackend.

mkoeppe · 2021-07-20T06:41:46Z

comment:39

Also no error with cbc from our outdated SPKG (2.9.4.p0).

mkoeppe · 2021-07-20T06:56:27Z

comment:40

However, I do get errors with the cbc from the upgrade ticket #30644 that looks like the original report!

mkoeppe · 2021-07-20T07:31:08Z

comment:41

That's a bug that will need investigating.

https://coin-or.github.io/Cbc/cbcmodelclass.html:

Primal column solution

const double * getColSolution()

The OSI method will return the best solution found thus far, unless none has been found. It is safer to use CbcModel version, CbcModel::bestSolution()"

dimpase · 2021-07-21T11:15:38Z

comment:44

g.minor() is buggy. E.g. with solver='ppl' is doesn't seem to terminate on

g = graphs.RandomGNP(20,.5)
g = g.subgraph(edges = g.min_spanning_tree())
g.minor(graphs.CompleteGraph(3), solver='ppl')

With 'glpk' instead of 'ppl' it's quick and correct (no such minor).

With Coin/cbc (from #30644, but do not forget to make sage_numerical_backends_coin)
it returns nonsense {0: [], 1: [0], 2: [17]}.

An interface bug? (both for PPL and Coin/cbc?)

mkoeppe · 2021-07-26T18:24:34Z

comment:45

Replying to @dimpase:

with solver='ppl' is doesn't seem to terminate

This is a MIP model with 117 binary variables, 344 total variables. Just way out of league for PPL. No bug here

mkoeppe · 2021-12-18T19:53:12Z

comment:47

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.

mkoeppe · 2022-07-30T23:50:13Z

comment:49

Obsolete after #30644

mkoeppe · 2022-07-30T23:50:13Z

Changed dependencies from #32197 #32218 #32219 #32220 #32221 #32222 #32223 #32224 #32225 #32236 #32237 #32238 #32239 #32240 #32241 to #30644

dcoudert · 2022-07-31T06:26:39Z

Reviewer: David Coudert

dcoudert · 2022-07-31T06:26:39Z

comment:50

So then.

seblabbe added this to the sage-9.2 milestone Sep 22, 2020

seblabbe added c: graph theory labels Sep 22, 2020

seblabbe changed the title ~~doctests failures in sage/graphs~~ doctests failures in sage/graphs when using COIN solver Sep 23, 2020

This comment has been minimized.

Sign in to view

mkoeppe added s: needs info and removed s: needs review labels Jul 20, 2021

mkoeppe added this to the sage-9.4 milestone Jul 20, 2021

mkoeppe added p: critical / 2 and removed p: major / 3 labels Jul 20, 2021

mkoeppe modified the milestones: sage-9.4, sage-9.5 Aug 22, 2021

mkoeppe modified the milestones: sage-9.5, sage-9.6 Dec 18, 2021

mkoeppe modified the milestones: sage-9.6, sage-9.7 Mar 5, 2022

mkoeppe added s: needs review and removed s: needs info labels Jul 30, 2022

mkoeppe removed this from the sage-9.7 milestone Jul 30, 2022

dcoudert added s: positive review and removed s: needs review labels Jul 31, 2022

mkoeppe removed the s: positive review label Aug 2, 2022

mkoeppe closed this as completed Aug 2, 2022

This was referenced Oct 21, 2022

meta-ticket: failing internet/optional doctests #25536

Open

Upgrade optional package cbc to 2.10.x, remove sage_numerical_backends_coin #30644

Open

doctests failures in sage/graphs when using COIN solver #30635

doctests failures in sage/graphs when using COIN solver #30635

Comments

seblabbe commented Sep 22, 2020

dcoudert commented Sep 22, 2020

seblabbe commented Sep 23, 2020

dcoudert commented Sep 23, 2020

seblabbe commented Sep 23, 2020

seblabbe commented Sep 23, 2020

This comment has been minimized.

dcoudert commented Sep 23, 2020

seblabbe commented Sep 23, 2020

seblabbe commented Sep 23, 2020

seblabbe commented Sep 23, 2020

dcoudert commented Sep 23, 2020

seblabbe commented Sep 23, 2020

mkoeppe commented Sep 23, 2020

seblabbe commented Sep 23, 2020

seblabbe commented Sep 23, 2020

seblabbe commented Sep 23, 2020

This comment has been minimized.

mkoeppe commented Sep 23, 2020

mkoeppe commented Sep 23, 2020

seblabbe commented Sep 23, 2020

dcoudert commented Sep 23, 2020

dcoudert commented Sep 23, 2020

mkoeppe commented Sep 23, 2020

dcoudert commented Sep 23, 2020

mkoeppe commented Sep 23, 2020

mkoeppe commented Jul 20, 2021

mkoeppe commented Jul 20, 2021

mkoeppe commented Jul 20, 2021

dimpase commented Jul 21, 2021

mkoeppe commented Jul 26, 2021

mkoeppe commented Dec 18, 2021

mkoeppe commented Jul 30, 2022

mkoeppe commented Jul 30, 2022

dcoudert commented Jul 31, 2022

dcoudert commented Jul 31, 2022