Opened 5 years ago

Closed 5 years ago

# Fractional Chromatic Index Infinite Loop

Reported by: Owned by: Fidel Barrera-Cruz major sage-8.1 graph theory graph-theory, LP David Coudert Dima Pasechnik N/A ceb0eb8

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

### comment:1 Changed 5 years ago by Dima Pasechnik

Authors: → Dima Pasechnik → u/dimpase/fracchromfix → 66322e3b99d59025cb8c385e9480a48c47bce90c LP added; GLPK removed new → needs_review

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

### comment:2 follow-up:  3 Changed 5 years ago by 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.

### comment:3 in reply to:  2 Changed 5 years ago by Dima Pasechnik

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 5 years ago by David Coudert

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

### comment:5 Changed 5 years ago by 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.

### comment:6 Changed 5 years ago by David Coudert

The branch I proposed seems solver independent.

Dima, what do you think?

### comment:7 Changed 5 years ago by Dima Pasechnik

Authors: Dima Pasechnik → David Coudert u/dimpase/fracchromfix → u/dcoudert/23658 66322e3b99d59025cb8c385e9480a48c47bce90c → dae20a3f42b82e228ca7a069eb04840b80615654

New commits:

 ​dae20a3 `trac #23658: use LP for the matching problem`

### comment:8 Changed 5 years ago by 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...

### comment:9 Changed 5 years ago by git

Commit: dae20a3f42b82e228ca7a069eb04840b80615654 → ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb

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

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

### comment:10 Changed 5 years ago by 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.

### comment:11 Changed 5 years ago by Dima Pasechnik

Reviewers: → Dima Pasechnik needs_review → positive_review

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

### comment:12 Changed 5 years ago by Volker Braun

Branch: u/dcoudert/23658 → ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb → fixed positive_review → closed

### comment:13 Changed 5 years ago by Jeroen Demeyer

Commit: ceb0eb87ab080f9329ed1f70a1396e63bd15f4cb

Follow-up: #23798

Note: See TracTickets for help on using tickets.