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: sage-8.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 jdemeyer)

The test

            sage: g = graphs.PetersenGraph()
            sage: g.fractional_chromatic_index(solver='GLPK')
            3.0

added in src/sage/graphs/graph.py by #23658 fails with GLPK-4.63 on 32-bit.

As a workaround, we use PPL by default in #24099.

Change History (16)

comment:1 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 3 years ago by jdemeyer

  • 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 dcoudert

I suspect that we need to change if M.solve(log = verbose) <= 1: to if M.solve(log = verbose) <= 1 + tol:, where tol = 0 if solver=='PPL' else 1e-6. I don't like this solution, but I don't know what else we can do.

I don't have access to a 32-bit machine and so cannot test.

comment:4 Changed 3 years ago by jdemeyer

You could also forbid using a non-exact solver for this problem.

comment:5 Changed 3 years ago by dcoudert

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 dcoudert

  • Authors set to David Coudert
  • 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:

7485007trac #23798: set PPL has default solver

comment:7 Changed 2 years ago by jdemeyer

  • Status changed from needs_review to needs_work

"Be aware that this method may loop endlessly when using some non exact solvers on 32-bits". I doubt that this is problem specific to 32 bits. The wording seems to imply that it's safe to use non-exact solvers on 64-bit machines.

comment:8 Changed 2 years ago by jdemeyer

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 git

  • Commit changed from 74850077e305024907037e4094f5956ef5a59e11 to 910fb839eb4612f42bf61858d0f0725fb1f2559c

Branch pushed to git repo; I updated commit sha1. New commits:

910fb83trac #23798: reviewers comments

comment:10 Changed 2 years ago by dcoudert

  • Status changed from needs_work to needs_review

Is this more appropriate ?

comment:11 Changed 2 years ago by jdemeyer

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 jdemeyer

  • Status changed from needs_review to needs_work

comment:13 follow-up: Changed 2 years ago by dcoudert

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 jdemeyer

  • Authors David Coudert deleted
  • Branch u/dcoudert/23798 deleted
  • Commit 910fb839eb4612f42bf61858d0f0725fb1f2559c deleted
  • Description modified (diff)

comment:15 in reply to: ↑ 13 Changed 2 years ago by jdemeyer

Replying to dcoudert:

The problem is not fixed.

Then I'm moving your branch to a new ticket: #24099.

comment:16 Changed 2 years ago by dcoudert

OK, thanks.

Note: See TracTickets for help on using tickets.