Ask Your Question
0

fractional_chromatic_index in sage-7.6 gets stuck in loop adding constraints

asked 2017-08-15 17:52:02 -0500

elbie gravatar image

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

1 answer

Sort by ยป oldest newest most voted
0

answered 2017-08-19 13:06:38 -0500

fidbc gravatar image

updated 2017-08-19 13:16:54 -0500

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 more

Comments

This is now ticket number 23658.

fidbc gravatar imagefidbc ( 2017-08-20 15:01:47 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-08-15 17:52:02 -0500

Seen: 36 times

Last updated: Aug 19