Opened 2 years ago

Closed 2 years ago

Last modified 2 years ago

#23658 closed defect (fixed)

Fractional Chromatic Index Infinite Loop

Reported by: fidelbarrera Owned by:
Priority: major Milestone: sage-8.1
Component: graph theory Keywords: graph-theory, LP
Cc: Merged in:
Authors: David Coudert Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: ceb0eb8 (Commits) 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 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/

Change History (13)

comment:1 Changed 2 years ago by dimpase

  • Authors set to Dima Pasechnik
  • Branch set to u/dimpase/fracchromfix
  • Commit set to 66322e3b99d59025cb8c385e9480a48c47bce90c
  • Keywords LP added; GLPK removed
  • Status changed from new to needs_review

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

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

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.

comment:3 in reply to: ↑ 2 Changed 2 years ago by dimpase

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.

comment:4 Changed 2 years ago by dcoudert

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

comment:5 Changed 2 years ago by jipilab

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 2 years ago by dcoudert

The branch I proposed seems solver independent.

Dima, what do you think?

comment:7 Changed 2 years ago by dimpase

  • Authors changed from Dima Pasechnik to David Coudert
  • Branch changed from u/dimpase/fracchromfix to u/dcoudert/23658
  • Commit changed from 66322e3b99d59025cb8c385e9480a48c47bce90c to dae20a3f42b82e228ca7a069eb04840b80615654

New commits:

dae20a3trac #23658: use LP for the matching problem

comment:8 Changed 2 years ago by dimpase

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 2 years ago by git

  • Commit changed from dae20a3f42b82e228ca7a069eb04840b80615654 to ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb

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

dda33fatrac #23658: Merged with 8.1.beta3
ceb0eb8trac #23658: test

comment:10 Changed 2 years ago by dcoudert

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 2 years ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

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

comment:12 Changed 2 years ago by vbraun

  • Branch changed from u/dcoudert/23658 to ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:13 Changed 2 years ago by jdemeyer

  • Commit ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb deleted

Follow-up: #23798

Note: See TracTickets for help on using tickets.