#23658 closed defect (fixed)
Fractional Chromatic Index Infinite Loop
Reported by:  Fidel BarreraCruz  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, 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 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 5 years ago by
Authors:  → Dima Pasechnik 

Branch:  → u/dimpase/fracchromfix 
Commit:  → 66322e3b99d59025cb8c385e9480a48c47bce90c 
Keywords:  LP added; GLPK removed 
Status:  new → needs_review 
comment:2 followup: 3 Changed 5 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 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 + 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 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 

Followup: #23798
The easiest fix is to set the default solver to PPL.