#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) | 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 4 years ago by
- Branch set to u/dimpase/fracchromfix
- Commit set to 66322e3b99d59025cb8c385e9480a48c47bce90c
- Keywords LP added; GLPK removed
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 4 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 in reply to: ↑ 2 Changed 4 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 4 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 4 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 4 years ago by
The branch I proposed seems solver independent.
Dima, what do you think?
comment:7 Changed 3 years ago by
- Branch changed from u/dimpase/fracchromfix to u/dcoudert/23658
- Commit changed from 66322e3b99d59025cb8c385e9480a48c47bce90c to dae20a3f42b82e228ca7a069eb04840b80615654
New commits:
dae20a3 | trac #23658: use LP for the matching problem
|
comment:8 Changed 3 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 3 years ago by
- Commit changed from dae20a3f42b82e228ca7a069eb04840b80615654 to ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb
comment:10 Changed 3 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 3 years ago by
- Reviewers set to Dima Pasechnik
- Status changed from needs_review to positive_review
OK, sorry, I overlooked it. It's good to go, thanks.
comment:12 Changed 3 years ago by
- Branch changed from u/dcoudert/23658 to ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb
- Resolution set to fixed
- Status changed from positive_review to closed
comment:13 Changed 3 years ago by
- Commit ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb deleted
Follow-up: #23798
The easiest fix is to set the default solver to PPL.