#23658 closed defect (fixed)
Fractional Chromatic Index Infinite Loop
Reported by: | fidelbarrera | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.1 |
Component: | graph theory | Keywords: | graph-theory, LP |
Cc: | Merged in: | ||
Authors: | David Coudert | Reviewers: | Dima Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | ceb0eb8 (Commits, GitHub, GitLab) | Commit: | |
Dependencies: | Stopgaps: |
Description
The implementation contains an infinite loop that is broken when a quantity is less than or equal to 1, however the loop never ends on the following input:
sage: g=graphs.PetersenGraph() sage: g.fractional_chromatic_index(solver="GLPK")
The problem seems to depend on the LP solver, using PPL seems to work just fine. Issue seems to be GLPK and CBC/Coin.
Relevant sage-devel thread at [1].
Relevant ask.sagemath thread at [2].
[1]: https://groups.google.com/forum/#!topic/sage-devel/hsKxANYAeQI
Change History (13)
comment:1 Changed 5 years ago by
Authors: | → Dima Pasechnik |
---|---|
Branch: | → u/dimpase/fracchromfix |
Commit: | → 66322e3b99d59025cb8c385e9480a48c47bce90c |
Keywords: | LP added; GLPK removed |
Status: | new → needs_review |
comment:2 follow-up: 3 Changed 5 years ago by
another fix is to change the stop condition to
if sum((x[2] for x in matching)) <= 1 + 1e-9: break
with GLPK, we add multiple times the same constraint
Adding a constraint on matching : [(0, 5, 0.9999999999999999), (1, 2, 3.3306690738754696e-16), (6, 9, 1.4802973661668753e-16)]
and we can check that
sage: M = [(0, 5, 0.999999999999), (1, 6, 9.999778782798785e-13), (7, 9, 2.0000667788622195e-12)] sage: round(sum(e[2] for e in M),10) 1.0 sage: round(sum(e[2] for e in M),11) 1.0 sage: round(sum(e[2] for e in M),12) 1.000000000002
This is similar with Coin and I believe that it could also happen with Cplex/Gurobi/...
on some graphs.
comment:3 Changed 5 years ago by
Replying to dcoudert:
another fix is to change the stop condition to
if sum((x[2] for x in matching)) <= 1 + 1e-9: break
these kinds of absolute bounds don't scale well. While I didn't try, I guess taking a sufficiently big example will render this broken, still.
There are several pointers in the source on how to improve it, perhaps they should be explored, on another ticket.
comment:4 Changed 5 years ago by
I have another version in u/dcoudert/23658
. It uses a LP for the matching problem which solved the issue.
comment:5 Changed 5 years ago by
So which branch should be used?
Choosing PPL
sounds reasonable since it is also the default in Polyhedron
. In the current branch, I see only some spacing missing. Otherwise, looks good.
comment:6 Changed 5 years ago by
The branch I proposed seems solver independent.
Dima, what do you think?
comment:7 Changed 5 years ago by
Authors: | Dima Pasechnik → David Coudert |
---|---|
Branch: | u/dimpase/fracchromfix → u/dcoudert/23658 |
Commit: | 66322e3b99d59025cb8c385e9480a48c47bce90c → dae20a3f42b82e228ca7a069eb04840b80615654 |
New commits:
dae20a3 | trac #23658: use LP for the matching problem
|
comment:8 Changed 5 years ago by
Sorry for sitting on this: I presume your approach is more efficient. Could we have more tests, in particular the example on the ticket ought to become a test, with a reference to this ticket...
comment:9 Changed 5 years ago by
Commit: | dae20a3f42b82e228ca7a069eb04840b80615654 → ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb |
---|
comment:10 Changed 5 years ago by
The ticket number of the test was wrong, but the test of this ticket is in the patch. I don't know which extra tests I could be added.
comment:11 Changed 5 years ago by
Reviewers: | → Dima Pasechnik |
---|---|
Status: | needs_review → positive_review |
OK, sorry, I overlooked it. It's good to go, thanks.
comment:12 Changed 5 years ago by
Branch: | u/dcoudert/23658 → ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
comment:13 Changed 5 years ago by
Commit: | ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb |
---|
Follow-up: #23798
The easiest fix is to set the default solver to PPL.