#23658 closed defect (fixed)
Fractional Chromatic Index Infinite Loop
Reported by:  fidelbarrera  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  graph theory  Keywords:  graphtheory, 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 sagedevel thread at [1].
Relevant ask.sagemath thread at [2].
[1]: https://groups.google.com/forum/#!topic/sagedevel/hsKxANYAeQI
Change History (13)
comment:1 Changed 3 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 followup: ↓ 3 Changed 3 years ago by
another fix is to change the stop condition to
if sum((x[2] for x in matching)) <= 1 + 1e9: break
with GLPK, we add multiple times the same constraint
Adding a constraint on matching : [(0, 5, 0.9999999999999999), (1, 2, 3.3306690738754696e16), (6, 9, 1.4802973661668753e16)]
and we can check that
sage: M = [(0, 5, 0.999999999999), (1, 6, 9.999778782798785e13), (7, 9, 2.0000667788622195e12)] 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 3 years ago by
Replying to dcoudert:
another fix is to change the stop condition to
if sum((x[2] for x in matching)) <= 1 + 1e9: 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 3 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 3 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 3 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
Followup: #23798
The easiest fix is to set the default solver to PPL.