Fractional Chromatic Index test fails with GLPK #23798

jdemeyer · 2017-09-07T11:51:23Z

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.

CC: @dcoudert

Component: graph theory

Author: David Coudert

Branch/Commit: public/graphs/23798_fractional_chromatic_index @ 43e8873

Reviewer: Dima Pasechnik

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

The text was updated successfully, but these errors were encountered:

dcoudert · 2017-09-07T13:31:06Z

comment:3

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.

jdemeyer · 2017-09-07T15:01:08Z

comment:4

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

dcoudert · 2017-09-07T17:09:36Z

comment:5

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.

dcoudert · 2017-10-21T08:51:35Z

comment:6

I don't see better solution than making PPL the default solver here.

New commits:

`7485007`	`trac #23798: set PPL has default solver`

dcoudert · 2017-10-21T08:51:35Z

Commit: 7485007

dcoudert · 2017-10-21T08:51:35Z

Author: David Coudert

dcoudert · 2017-10-21T08:51:35Z

Branch: u/dcoudert/23798

jdemeyer · 2017-10-22T20:05:52Z

comment:7

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

jdemeyer · 2017-10-22T20:07:28Z

comment:8

Also, this isn't quite correct:

Tickets :trac:`23658` and :trac:`23798` are fixed::

followed by a test with GLPK.

sagetrac-git · 2017-10-22T21:23:58Z

Changed commit from 7485007 to 910fb83

sagetrac-git · 2017-10-22T21:23:58Z

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

`910fb83`	`trac #23798: reviewers comments`

dcoudert · 2017-10-22T21:24:39Z

comment:10

Is this more appropriate ?

jdemeyer · 2017-10-23T07:19:54Z

comment:11

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.

dcoudert · 2017-10-23T20:05:43Z

comment:13

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?

jdemeyer · 2017-10-24T17:17:49Z

Changed commit from 910fb83 to none

dcoudert · 2021-07-13T14:39:47Z

comment:27

Following above discussion, I added a tolerance gap for numerical LP solvers.

Note that we can use the networkx implementation of the blossom algorithm via the matching method, but it does not solve the issue. Actually, it's slower and worse for the rounding as I observe the issue on a 64 bits machine...

New commits:

`ebcde7c`	`trac #23798: add tolerance gap for numerical LP solvers`

dimpase · 2021-07-13T22:15:01Z

comment:28

I don’t like this approach. Without explicit guarantees that these tolerances are correct, it is replacing correct algorithms with heuristics.

mkoeppe · 2021-07-13T22:21:48Z

comment:29

         matching = [fe for fe in frozen_edges if M.get_values(b[fe]) == 1]

This line also needs changing because the test "== 1" is not robust.

dimpase · 2021-07-13T22:48:31Z

comment:30

I don’t see how one can make the oracle (the inner LP) inexact, without potentially returning a very wrong answer.

The oracle checks that there is no maximum weight matching of weight >1. Say, we let it error by epsilon, i.e we terminate with oracle returning 1+epsilon. Potentially, there could be K maximum matchings with this weight, if they are disjoint this means that the final error is K times epsilon, oops…

dimpase · 2021-07-13T22:50:28Z

Reviewer: Dima Pasechnik

dcoudert · 2021-07-14T10:48:34Z

comment:32

I don't like this solution either but I don't know what to do when a solver returns 0.99999... instead of 1 although we have set the variable type to binary. The solvers are aware of the type of the variable and so should return a value with the correct type and not a double. The solution might be in the backends.

dimpase · 2021-07-14T21:48:02Z

comment:33

Replying to @dcoudert:

I don't like this solution either but I don't know what to do when a solver returns 0.99999... instead of 1 although we have set the variable type to binary. The solvers are aware of the type of the variable and so should return a value with the correct type and not a double. The solution might be in the backends.

No, my point is that without a special analysis it's not possible to argue that solving the oracle problem (with non-integer objective function) inexactly provides a correct result, even if you "correctly" round 0.9999... to 1. It's because a small oracle error may get amplified a lot in the main LP.
Welcome to floating point hell :-)|

dimpase · 2021-07-15T12:24:24Z

comment:34

Replying to @dcoudert:

Following above discussion, I added a tolerance gap for numerical LP solvers.

Note that we can use the networkx implementation of the blossom algorithm via the matching method, but it does not solve the issue. Actually, it's slower and worse for the rounding as I observe the issue on a 64 bits machine...

The oracle implementation here is naive, and bound to get very slow; it's integer LP without Edmonds' constraints,
instead of a "normal" LP over the matching polytope with Edmonds' constraints (aka blossom inequalities).
So this would need yet another oracle (as there are too exponentially many inequalities there), but well, it's polynomial time then.
The generated constraints can stay, so this should be fast.

New commits:

`ebcde7c`	`trac #23798: add tolerance gap for numerical LP solvers`

mkoeppe · 2021-07-19T14:24:43Z

comment:35

I took a quick look at the function now. I would suggest the following changes:

Before adding a new constraint to the master problem, verify that matching is indeed a matching. In this way, the master problem will always be a correct relaxation, even if an inexact oracle is used.
When the numerical solver that is used for solving the separation problem does not find a matching of value greater than 1 + epsilon, you can switch to PPL - then, with a bit of luck, it can prove the bound <= 1.
It will make sense to have separate parameters for the solver used for the master problem and the one(s) used for the separation problem.

dimpase · 2021-07-19T17:25:03Z

comment:36

Actually, it seems that even with PPL, the code is just wrong, as PPL does not do MILP, it only does LP, right?

mkoeppe · 2021-07-19T18:35:21Z

comment:37

The PPL does have a (very limited) MIP solver.

sagetrac-git · 2021-11-06T16:25:16Z

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

`1926be5`	`trac #23798: merged with 9.5.beta5`
`43e8873`	`trac #23798: ideas from comment 35`

sagetrac-git · 2021-11-06T16:25:16Z

Changed commit from ebcde7c to 43e8873

dcoudert · 2021-11-06T16:28:16Z

comment:40

I tried the ideas from #comment:35. I have let some code for debugging as the code may loop forever when using GLPK for both master and separation problems. The patchbot will complain...

We should search for another method not relying on LP solvers, if any...

jdemeyer added this to the sage-8.1 milestone Sep 7, 2017

jdemeyer added c: graph theory labels Sep 7, 2017

This comment has been minimized.

Sign in to view

jdemeyer changed the title ~~Fractional Chromatic Index Infinite Loop fails with GLPK~~ Fractional Chromatic Index test fails with GLPK Sep 7, 2017

dcoudert added the s: needs review label Oct 21, 2017

jdemeyer added s: needs work and removed s: needs review labels Oct 22, 2017

dcoudert added s: needs review and removed s: needs work labels Oct 22, 2017

jdemeyer added s: needs work and removed s: needs review labels Oct 23, 2017

This comment has been minimized.

Sign in to view

dcoudert added s: needs review and removed s: needs work labels Jul 13, 2021

dimpase added s: needs work and removed s: needs review labels Jul 13, 2021

mkoeppe modified the milestones: sage-9.4, sage-9.5 Aug 9, 2021

mkoeppe modified the milestones: sage-9.5, sage-9.6 Jan 10, 2022

mkoeppe modified the milestones: sage-9.6, sage-9.7 Apr 11, 2022

mkoeppe modified the milestones: sage-9.7, sage-9.8 Aug 31, 2022

mkoeppe removed this from the sage-9.8 milestone Jan 29, 2023

jdemeyer mentioned this issue Oct 30, 2017

Use PPL by default for Fractional Chromatic Index #24099

Closed

mkoeppe mentioned this issue Jan 29, 2023

Meta-ticket: Audit/fix all uses of MixedIntegerLinearProgram #32191

Open

ed359 mentioned this issue Jun 4, 2023

GLPK/exact isn't exact on simple, rational LPs #35727

Closed

2 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fractional Chromatic Index test fails with GLPK #23798

Fractional Chromatic Index test fails with GLPK #23798

jdemeyer commented Sep 7, 2017

This comment has been minimized.

This comment has been minimized.

dcoudert commented Sep 7, 2017

jdemeyer commented Sep 7, 2017

dcoudert commented Sep 7, 2017

dcoudert commented Oct 21, 2017

dcoudert commented Oct 21, 2017

dcoudert commented Oct 21, 2017

dcoudert commented Oct 21, 2017

jdemeyer commented Oct 22, 2017

jdemeyer commented Oct 22, 2017

sagetrac-git mannequin commented Oct 22, 2017

sagetrac-git mannequin commented Oct 22, 2017

dcoudert commented Oct 22, 2017

jdemeyer commented Oct 23, 2017

dcoudert commented Oct 23, 2017

jdemeyer commented Oct 24, 2017

This comment has been minimized.

dcoudert commented Jul 13, 2021

dimpase commented Jul 13, 2021

mkoeppe commented Jul 13, 2021

dimpase commented Jul 13, 2021

dimpase commented Jul 13, 2021

dcoudert commented Jul 14, 2021

dimpase commented Jul 14, 2021

dimpase commented Jul 15, 2021

mkoeppe commented Jul 19, 2021

dimpase commented Jul 19, 2021

mkoeppe commented Jul 19, 2021

sagetrac-git mannequin commented Nov 6, 2021

sagetrac-git mannequin commented Nov 6, 2021

dcoudert commented Nov 6, 2021

Fractional Chromatic Index test fails with GLPK #23798

Fractional Chromatic Index test fails with GLPK #23798

Comments

jdemeyer commented Sep 7, 2017

This comment has been minimized.

This comment has been minimized.

dcoudert commented Sep 7, 2017

jdemeyer commented Sep 7, 2017

dcoudert commented Sep 7, 2017

dcoudert commented Oct 21, 2017

dcoudert commented Oct 21, 2017

dcoudert commented Oct 21, 2017

dcoudert commented Oct 21, 2017

jdemeyer commented Oct 22, 2017

jdemeyer commented Oct 22, 2017

sagetrac-git mannequin commented Oct 22, 2017

sagetrac-git mannequin commented Oct 22, 2017

dcoudert commented Oct 22, 2017

jdemeyer commented Oct 23, 2017

dcoudert commented Oct 23, 2017

jdemeyer commented Oct 24, 2017

This comment has been minimized.

dcoudert commented Jul 13, 2021

dimpase commented Jul 13, 2021

mkoeppe commented Jul 13, 2021

dimpase commented Jul 13, 2021

dimpase commented Jul 13, 2021

dcoudert commented Jul 14, 2021

dimpase commented Jul 14, 2021

dimpase commented Jul 15, 2021

mkoeppe commented Jul 19, 2021

dimpase commented Jul 19, 2021

mkoeppe commented Jul 19, 2021

sagetrac-git mannequin commented Nov 6, 2021

sagetrac-git mannequin commented Nov 6, 2021

dcoudert commented Nov 6, 2021