Fractional Chromatic Index Infinite Loop

[sagetrac-fidelbarrera]

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.

Component: graph theory

Keywords: graph-theory

Author: David Coudert

Branch: ceb0eb8

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/23658

[dimpase]

comment:1

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

[dimpase]

Branch: u/dimpase/fracchromfix

[dimpase]

Commit: 66322e3

[dimpase]

Author: Dima Pasechnik

[dimpase]

Changed keywords from GLPK, graph-theory to graph-theory

[dcoudert]

comment:2

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.

[dimpase]

comment:3

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.

[dcoudert]

comment:4

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

[jplab]

comment:5

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.

[dcoudert]

comment:6

The branch I proposed seems solver independent.

Dima, what do you think?

[dimpase]

Changed commit from 66322e3 to dae20a3

[dimpase]

Changed branch from u/dimpase/fracchromfix to u/dcoudert/23658

[dimpase]

Changed author from Dima Pasechnik to David Coudert

[dimpase]

New commits:

dae20a3

trac #23658: use LP for the matching problem

[dimpase]

comment:8

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

[sagetrac-git]

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

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

[sagetrac-git]

Changed commit from dae20a3 to ceb0eb8

[dcoudert]

comment:10

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.

[dimpase]

comment:11

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

[dimpase]

Reviewer: Dima Pasechnik

[vbraun]

Changed branch from u/dcoudert/23658 to ceb0eb8

[jdemeyer]

comment:13

Follow-up: #23798

[jdemeyer]

Changed commit from ceb0eb8 to none