doctests failures in sage/graphs when using COIN solver

[Sébastien Labbé]

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 

[David Coudert]

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.

[Sébastien Labbé]

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

[David Coudert]

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.

[Sébastien Labbé]

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}

[Sébastien Labbé]

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

[David Coudert]

Replying to slabbe:

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

not sure. See #29551

[Sébastien Labbé]

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)

[Sébastien Labbé]

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!
----------------------------------------------------------------------

[Sébastien Labbé]

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...

[David Coudert]

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.

[Sébastien Labbé]

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 ?

[Matthias Köppe]

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.

[Sébastien Labbé]

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.

[Sébastien Labbé]

and the ​latest release version of Cbc is 2.10.5

[Sébastien Labbé]

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?

[Matthias Köppe]

Replying to slabbe:

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...

[Matthias Köppe]

Replying to slabbe:

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.

[Sébastien Labbé]

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

[David Coudert]

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.

[David Coudert]

Replying to slabbe:

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

[Matthias Köppe]

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.

[David Coudert]

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 ?

[Matthias Köppe]

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.

[Matthias Köppe]

Any doctests using this solver should be marked optional - sage_numerical_backends_coin, by the way (see #30646). Installing cbc by itself does not trigger installation of sage_numerical_backends_coin.

[Matthias Köppe]

I would suggest to create a helper function that converts an inexact 0/1 output to bool with error margin checking, and to use it throughout the sage.graphs package. Define a small epsilon, say 1e-4. Error out if input is away from 0 or 1 by something larger than that epsilon -- this indicates either a modeling error or a severe numerical issue in the solver.

[Sébastien Labbé]

related to the suggestion of Matthias, I see that the following change was made in #28689:

     cpdef get_variable_value(self, int variable):
         r"""
@@ -868,7 +868,7 @@ cdef class CoinBackend(GenericBackend):
         if self.is_variable_continuous(variable):
             return v
         else:
-            return round(v)
+            return int(round(v))
 
     cpdef int ncols(self):
         r"""

[Matthias Köppe]

I don't support attempts of this kind to clean up the floating point results in the solver backends or in the MixedIntegerLinearProgram front-end. There is no generally correct way to exactify a solution to a MIP.

MixedIntegerLinearProgram has the notion of a base_ring, which is RDF in the case of the numerical solvers. Client code of MixedIntegerLinearProgram needs to handle floating point results in a model-specific way.

[Matthias Köppe]

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[Matthias Köppe]

Replying to mkoeppe:

I would suggest to create a helper function that converts an inexact 0/1 output to bool with error margin checking, and to use it throughout the sage.graphs package. Define a small epsilon, say 1e-4. Error out if input is away from 0 or 1 by something larger than that epsilon -- this indicates either a modeling error or a severe numerical issue in the solver.

This is now available with #32197. Meta-ticket #32191 (Audit/fix all uses of MixedIntegerLinearProgram) tracks the necessary changes in the library

[David Coudert]

Does #32239 (which depends on #32197) fix the issues in graph.py ?

[Matthias Köppe]

I haven't tested anything with COIN, but it is likely that these are all symptoms of the same issue that we're addressing in #32191.

[Matthias Köppe]

No error with sage_numerical_backends_coin installed with the above tickets from #32191 merged. This is with cbc 2.10.3 from homebrew.

[Matthias Köppe]

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

[Matthias Köppe]

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

[Matthias Köppe]

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()"

[Dima Pasechnik]

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?)

[Matthias Köppe]

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

[Matthias Köppe]

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

[Matthias Köppe]

Obsolete after #30644

[David Coudert]

So then.