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

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 close merge delete

Sort by » oldest newest most voted

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):

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.

more

This is now ticket number 23658.

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