Opened 2 years ago
Closed 6 months ago
#30635 closed defect (invalid)
doctests failures in sage/graphs when using COIN solver
Reported by: | Sébastien Labbé | Owned by: | |
---|---|---|---|
Priority: | critical | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | |
Cc: | Matthias Köppe, Dima Pasechnik | Merged in: | |
Authors: | Reviewers: | David Coudert | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #30644 | Stopgaps: |
Description (last modified by )
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
Change History (51)
comment:1 Changed 2 years ago by
comment:2 Changed 2 years ago by
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
comment:3 Changed 2 years ago by
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.
comment:4 follow-up: 20 Changed 2 years ago by
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}
comment:5 Changed 2 years ago by
Summary: | doctests failures in sage/graphs → doctests failures in sage/graphs when using COIN solver |
---|
comment:7 Changed 2 years ago by
Description: | modified (diff) |
---|
comment:8 Changed 2 years ago by
comment:9 Changed 2 years ago by
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)
comment:10 Changed 2 years ago by
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! ----------------------------------------------------------------------
comment:11 Changed 2 years ago by
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...
comment:12 Changed 2 years ago by
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.
comment:13 Changed 2 years ago by
Cc: | Matthias Köppe added |
---|
adding Matthias in cc here. Questions are:
- is it normal to have
sage_numerical_backends_coin
installed but notcbc
(this is the source of the bug in this ticket)? - is it normal that
--enable-cbc
in the configuration did not installedcbc
?
comment:14 follow-up: 17 Changed 2 years ago by
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.
comment:15 Changed 2 years ago by
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
.
comment:17 follow-up: 19 Changed 2 years ago by
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
?
comment:18 Changed 2 years ago by
Description: | modified (diff) |
---|
comment:19 Changed 2 years ago by
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
...
comment:20 follow-up: 22 Changed 2 years ago by
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.
comment:21 follow-up: 23 Changed 2 years ago by
Testing with cbc 2.10.5 (upgrade at #30644), the doctest failure stays.
comment:22 follow-up: 24 Changed 2 years ago by
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.
comment:23 Changed 2 years ago by
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
comment:24 Changed 2 years ago by
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 usevertex_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.
comment:25 follow-up: 26 Changed 2 years ago by
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 ?
comment:26 Changed 2 years ago by
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 notcoin
, 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
.
comment:27 Changed 2 years ago by
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
.
comment:28 follow-up: 35 Changed 2 years ago by
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.
comment:29 Changed 2 years ago by
Priority: | major → critical |
---|
comment:30 Changed 2 years ago by
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"""
comment:31 Changed 2 years ago by
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.
comment:32 Changed 2 years ago by
Milestone: | sage-9.2 → sage-9.3 |
---|
comment:33 Changed 2 years ago by
Milestone: | sage-9.3 → sage-9.4 |
---|
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:34 Changed 19 months ago by
Dependencies: | → #32191 |
---|
comment:35 Changed 19 months ago by
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
comment:36 Changed 19 months ago by
comment:37 Changed 19 months ago by
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.
comment:38 Changed 19 months ago by
Dependencies: | #32191 → #32197 #32218 #32219 #32220 #32221 #32222 #32223 #32224 #32225 #32236 #32237 #32238 #32239 #32240 #32241 |
---|---|
Milestone: | sage-9.4 → sage-duplicate/invalid/wontfix |
Priority: | critical → major |
Status: | new → needs_review |
No error with sage_numerical_backends_coin
installed with the above tickets from #32191 merged. This is with cbc
2.10.3 from homebrew.
comment:40 Changed 19 months ago by
Status: | needs_review → needs_info |
---|
However, I do get errors with the cbc
from the upgrade ticket #30644 that looks like the original report!
comment:41 Changed 19 months ago by
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()"
comment:42 Changed 19 months ago by
Milestone: | sage-duplicate/invalid/wontfix → sage-9.4 |
---|---|
Priority: | major → critical |
comment:43 Changed 19 months ago by
Cc: | Dima Pasechnik added |
---|
comment:44 follow-up: 45 Changed 19 months ago by
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?)
comment:45 Changed 18 months ago by
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
comment:46 Changed 17 months ago by
Milestone: | sage-9.4 → sage-9.5 |
---|
comment:47 Changed 13 months ago by
Milestone: | sage-9.5 → sage-9.6 |
---|
Stalled in needs_review
or needs_info
; likely won't make it into Sage 9.5.
comment:48 Changed 11 months ago by
Milestone: | sage-9.6 → sage-9.7 |
---|
comment:49 Changed 6 months ago by
Dependencies: | #32197 #32218 #32219 #32220 #32221 #32222 #32223 #32224 #32225 #32236 #32237 #32238 #32239 #32240 #32241 → #30644 |
---|---|
Milestone: | sage-9.7 → sage-duplicate/invalid/wontfix |
Status: | needs_info → needs_review |
Obsolete after #30644
comment:50 Changed 6 months ago by
Reviewers: | → David Coudert |
---|---|
Status: | needs_review → positive_review |
So then.
comment:51 Changed 6 months ago by
Resolution: | → invalid |
---|---|
Status: | positive_review → closed |
I suspect it is due to coin. Can you try for instance
fedora 32, with cplex as default solver, I get
same on macOS 10.15.6 but with only cplex as optional package.