fractional_chromatic_index in sage-7.6 gets stuck in loop adding constraints

asked 2017-08-16 00:52:02 +0200

elbie

3 ●2

updated 2019-01-09 17:57:42 +0200

FrédéricC

5125 ●3 ●43 ●111

I have a researcher that's trying to use fractional_chromatic_index, but depending on the solver used, it appears to get stuck in an endless loop adding constraints. For example, the PPL solver works fine:

sage: g=graphs.PetersenGraph()
sage: g.fractional_chromatic_index(solver="PPL")
3

But if I use the default (GLPK) or the CBC/Coin solver, it just seems to hang. By adding verbose_constraints=1 as an option, you can see that it just goes and goes and goes:

sage: g.fractional_chromatic_index(solver="glpk",verbose_constraints=1)
Adding a constraint on matching : [(0, 5, 1.0), (1, 6, 1.0), (2, 7, 1.0), (3, 8, 1.0), (4, 9, 1.0)]
Adding a constraint on matching : [(0, 5, 1.0), (1, 2, 1.0), (3, 4, 1.0), (6, 8, 1.0), (7, 9, 1.0)]
Adding a constraint on matching : [(0, 4, 1.0), (2, 3, 1.0), (5, 8, 1.0), (6, 9, 1.0)]
Adding a constraint on matching : [(0, 4, 1.0), (1, 6, 1.0), (5, 7, 1.0)]
Adding a constraint on matching : [(0, 1, 1.0), (2, 3, 1.0), (5, 7, 1.0)]
Adding a constraint on matching : [(1, 6, 1.0), (5, 8, 1.0)]
Adding a constraint on matching : [(0, 4, 0.5), (1, 2, 1.0), (5, 8, 0.5)]
Adding a constraint on matching : [(0, 1, 1.0), (2, 7, 0.5), (3, 4, 1.0), (5, 8, 0.5)]
Adding a constraint on matching : [(6, 9, 1.0), (1, 2, 1.0)]
Adding a constraint on matching : [(0, 1, 1.0), (3, 8, 0.5), (6, 9, 0.5)]
Adding a constraint on matching : [(0, 1, 1.0), (4, 9, 1.0), (6, 8, 1.0)]
Adding a constraint on matching : [(0, 4, 0.25), (1, 2, 0.5), (3, 8, 0.25), (5, 7, 0.75), (6, 9, 0.5)]
Adding a constraint on matching : [(1, 6, 0.5000000000000001), (2, 3, 5.551115123125783e-17), (5, 8, 0.5), (7, 9, 1.0)]
Adding a constraint on matching : [(0, 1, 0.3333333333333333), (3, 4, 0.6666666666666666), (5, 7, 0.33333333333333337), (6, 9, 0.3333333333333334)]
Adding a constraint on matching : [(0, 4, 0.33333333333333437), (2, 3, 0.3333333333333328), (6, 8, 0.6666666666666642), (7, 9, 0.33333333333333626)]
Adding a constraint on matching : [(2, 3, 0.1999999999999997), (4, 9, 0.5999999999999989), (5, 7, 0.8000000000000005), (6, 8, 0.40000000000000113)]
Adding a constraint on matching : [(0, 4, 0.49999999999999994), (1, 2, 1.6653345369377348e-16), (5, 8, 0.5000000000000001), (7, 9, 0.5)]
Adding a constraint on matching : [(0, 1, 0.5), (2, 3, 0.1666666666666668), (4, 9, 0.1666666666666666), (5, 7, 0.33333333333333326), (6, 8, 0.33333333333333337)]
Adding a constraint on matching : [(0, 1, 0.5999999999999998), (2, 7, 0.20000000000000012), (5, 8, 0.20000000000000018), (6, 9, 0.4000000000000003)]
Adding a constraint on matching : [(0, 4, 0.4374999999999998), (1, 6, 0.5625), (5, 8, 0.2500000000000003), (7, 9, 0.18750000000000006)]
Adding a constraint on matching : [(0, 1, 0.33333333333333326), (2, 7, 0.3333333333333335), (3, 4, 0.33333333333333315), (6, 9, 0.3333333333333335)]
Adding a constraint on matching : [(0, 1, 0.6249999999999999), (2, 3, 0.3750000000000001), (5, 8, 0.125), (7, 9, 0.2499999999999999)]
Adding a constraint on matching : [(0, 4, 0.4999999999999999), (1, 6, 0.5), (2, 3, 0.5000000000000001)]
Adding a constraint on matching : [(0, 1, 0.4999999999999994), (2, 7, 8.326672684688677e-17), (3, 4, 0.2500000000000002), (5, 8, 0.2500000000000003), (6, 9, 0.25000000000000044)]
Adding a constraint on matching : [(0, 4, 0.3999999999999996), (1, 6, 0.20000000000000012), (2, 3, 0.40000000000000024), (5, 7, 0.40000000000000024)]
Adding a constraint on matching : [(0, 4, 0.39999999999999936), (1, 6, 0.20000000000000026), (2, 3, 0.40000000000000036), (5, 8, 0.20000000000000018), (7, 9, 0.1999999999999999)]
Adding a constraint on matching : [(0, 5, 0.9999999999999999), (1, 2, 3.3306690738754696e-16), (6, 9, 1.4802973661668753e-16)]
Adding a constraint on matching : [(0, 5, 0.9999999999999999), (1, 2, 3.3306690738754696e-16), (6, 9, 1.4802973661668753e-16)]
Adding a constraint on matching : [(0, 5, 0.9999999999999999), (1, 2, 3.3306690738754696e-16), (6, 9, 1.4802973661668753e-16)]
...

I tried this on both the prebuilt OSX command-line build as well as the linux source tarball.

Any idea what's going on here?

edit retag flag offensive close merge delete

add a comment

answered 2017-08-19 20:06:38 +0200

fidbc

2423 ●4 ●26 ●61

updated 2017-08-19 20:16:54 +0200

Somehow looks like the numerical precision is not allowing the process to go through. The condition to stop the infinite loop is that the sum of the labels in the matching adds up to 1, in your case:
0.9999999999999999 + 3.3306690738754696e-16+ 1.4802973661668753e-16

However this evaluates to a number that is slightly above 1, this matching is produced over and over ever after. Below is some code to allow eps tolerance to the comparison to 1 so that the loop can be broken. This code is a tweaked copy of the code for fractional_chromatic_index that ships with SageMath. In the meantime this will be reported as a bug in the sage-devel mailing list, thanks for reporting!

def fract_chromatic_index(h,solver = None, verbose_constraints = 0, verbose = 0, eps=0.00000001):
    from sage.numerical.mip import MixedIntegerLinearProgram

    g = copy(h)
    p = MixedIntegerLinearProgram(solver=solver, constraint_generation = True)

    # One variable per edge
    r = p.new_variable(nonnegative=True)
    R = lambda x,y : r[x,y] if x<y else r[y,x]

    # We want to maximize the sum of weights on the edges
    p.set_objective( p.sum( R(u,v) for u,v in g.edges(labels = False)))

    # Each edge being by itself a matching, its weight can not be more than
    # 1

    for u,v in g.edges(labels = False):
        p.add_constraint( R(u,v), max = 1)

    obj = p.solve(log = verbose)
    while True:
        # Updating the value on the edges of g
        for u,v in g.edges(labels = False):
            g.set_edge_label(u,v,p.get_values(R(u,v)))

        # Computing a matching of maximum weight...
        matching = g.matching(use_edge_labels=True)

        # If the maximum matching has weight at most 1, we are done !
        if sum((x[2] for x in matching)) <= 1.0+eps:
            break

        #print "sum((x[2] for x in matching)): {0}; type: {1}".format(sum((x[2] for x in matching)),type(sum((x[2] for x in matching))))
        #print "sum((x[2] for x in matching)) <= 1.0 ? {0}".format(sum((x[2] for x in matching))<=1.0)
        #print matching
        #sleep(1)
        # Otherwise, we add a new constraint
        if verbose_constraints:
            print("Adding a constraint on matching : {}".format(matching))

        p.add_constraint( p.sum( R(u,v) for u,v,_ in matching), max = 1)
        # And solve again
        obj = p.solve(log = verbose)

    # Accomplished !
    return obj

This allows for

h=graphs.PetersenGraph()
fractional_chromatic_index(h,solver="Glpk")

to output 2.9999999999999996.

edit flag offensive delete link

Comments

This is now ticket number 23658.

fidbc ( 2017-08-20 22:01:47 +0200 )edit

add a comment

fractional_chromatic_index in sage-7.6 gets stuck in loop adding constraints

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

fractional_chromatic_index in sage-7.6 gets stuck in loop adding constraints edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

fractional_chromatic_index in sage-7.6 gets stuck in loop adding constraints