Opened 3 years ago
Last modified 2 years ago
#23798 needs_work defect
Fractional Chromatic Index test fails with GLPK
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  graph theory  Keywords:  
Cc:  dcoudert  Merged in:  
Authors:  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
Change History (16)
comment:1 Changed 3 years ago by
 Description modified (diff)
comment:2 Changed 3 years ago by
 Description modified (diff)
 Summary changed from Fractional Chromatic Index Infinite Loop fails with GLPK to Fractional Chromatic Index test fails with GLPK
comment:3 Changed 3 years ago by
comment:4 Changed 3 years ago by
You could also forbid using a nonexact solver for this problem.
comment:5 Changed 3 years ago by
Sure, we can force PPL
, but it is way slower (can sometimes be faster on small graphs).
sage: G = graphs.Grid2dGraph(6,6) sage: %time G.fractional_chromatic_index(solver='GLPK') CPU times: user 43.4 ms, sys: 4.9 ms, total: 48.3 ms Wall time: 52.1 ms 4.0 sage: %time G.fractional_chromatic_index(solver='PPL') CPU times: user 1min 11s, sys: 256 ms, total: 1min 11s Wall time: 1min 12s 4
I agree that using a tolerance gap is not a nice solution either.
comment:6 Changed 2 years ago by
 Branch set to u/dcoudert/23798
 Commit set to 74850077e305024907037e4094f5956ef5a59e11
 Status changed from new to needs_review
I don't see better solution than making PPL
the default solver here.
New commits:
7485007  trac #23798: set PPL has default solver

comment:7 Changed 2 years ago by
 Status changed from needs_review to needs_work
"Be aware that this method may loop endlessly when using some non exact solvers on 32bits". I doubt that this is problem specific to 32 bits. The wording seems to imply that it's safe to use nonexact solvers on 64bit machines.
comment:8 Changed 2 years ago by
Also, this isn't quite correct:
Tickets :trac:`23658` and :trac:`23798` are fixed::
followed by a test with GLPK.
comment:9 Changed 2 years ago by
 Commit changed from 74850077e305024907037e4094f5956ef5a59e11 to 910fb839eb4612f42bf61858d0f0725fb1f2559c
Branch pushed to git repo; I updated commit sha1. New commits:
910fb83  trac #23798: reviewers comments

comment:10 Changed 2 years ago by
 Status changed from needs_work to needs_review
Is this more appropriate ?
comment:11 Changed 2 years ago by
Well, it depends. Do you consider the code here to be a fix or a workaround? I am asking because you need to decide what to do with
sage: g.fractional_chromatic_index(solver='GLPK') # known bug (#23798)
You cannot say that this ticket is a known bug while at the same time fixing this ticket.
comment:12 Changed 2 years ago by
 Status changed from needs_review to needs_work
comment:13 followup: ↓ 15 Changed 2 years ago by
The problem is not fixed. That's why I changed the text to Issue reported in :trac:`23658` and :trac:`23798` with non exact solvers::
. What else can I write to be more correct/specific?
comment:14 Changed 2 years ago by
 Branch u/dcoudert/23798 deleted
 Commit 910fb839eb4612f42bf61858d0f0725fb1f2559c deleted
 Description modified (diff)
comment:15 in reply to: ↑ 13 Changed 2 years ago by
comment:16 Changed 2 years ago by
OK, thanks.
I suspect that we need to change
if M.solve(log = verbose) <= 1:
toif M.solve(log = verbose) <= 1 + tol:
, wheretol = 0 if solver=='PPL' else 1e6
. I don't like this solution, but I don't know what else we can do.I don't have access to a 32bit machine and so cannot test.