Fractional Chromatic Index Infinite Loop

[Fidel Barrera-Cruz]

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

[2]: ​https://ask.sagemath.org/question/38543/fractional_chromatic_index-in-sage-76-gets-stuck-in-loop-adding-constraints/

[Dima Pasechnik]

The easiest fix is to set the default solver to PPL.

[David Coudert]

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.

[Dima Pasechnik]

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.

[David Coudert]

I have another version in u/dcoudert/23658. It uses a LP for the matching problem which solved the issue.

[Jean-Philippe Labbé]

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.

[David Coudert]

The branch I proposed seems solver independent.

Dima, what do you think?

[Dima Pasechnik]

New commits:

​dae20a3

trac #23658: use LP for the matching problem

[Dima Pasechnik]

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...

[git]

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

​dda33fa	trac #23658: Merged with 8.1.beta3
​ceb0eb8	trac #23658: test

[David Coudert]

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.

[Dima Pasechnik]

OK, sorry, I overlooked it. It's good to go, thanks.

[Jeroen Demeyer]

Follow-up: #23798