Nathann COHEN
CNRS Researcher
ALGO Research Group
Laboratoire de Recherche en Informatique
nathann dot cohen 'at' gmail dot com


I stopped contributing to Sage since SageMath Inc. is a for-profit Delaware company with an actual self-appointed CEO whose top priority is to "make a lot of money". The website sagemath.com steals traffic from sagemath.org to promote SageMath Inc’s products, and SageMath Inc. takes its orders from unknown investors while free contributors to Sage have no say in the matter.

I did not spend years’ worth of nights and week-end writing open-source code so that private individuals will get richer. My government does not pay me to be the free workforce of a private for-profit company either.

Some LP Formulations
(and their Sage code)

Independent Set
Maximum set of pairwise non-adjacent vertices in a graph
p = MixedIntegerLinearProgram(maximization = True)
b = p.new_variable(binary = True)
p.set_objective( sum([b[v] for v in g]) )

for u,v in g.edges(labels = False):
    p.add_constraint( b[u] + b[v] <= 1 )

p.solve()
b = p.get_values(b)
print [v for v,i in b.items() if i]
Dominating Set
Minimum set of vertices whose neighborhood is the whole graph
p = MixedIntegerLinearProgram(maximization = False)
b = p.new_variable(binary = True)
p.set_objective( sum([b[v] for v in g]) )

for u in g:
    p.add_constraint( b[u] + sum([b[v] for v in g.neighbors(u)]) >= 1 )

p.solve()
b = p.get_values(b)
print [v for v,i in b.items() if i]
Vertex Cover
Minimum Set of vertices touching each edge
p = MixedIntegerLinearProgram(maximization = False)
b = p.new_variable(binary = True)
p.set_objective( sum([b[v] for v in g]) )

for u,v in g.edges(labels = False):
    p.add_constraint( b[u] + b[v] >= 1 )

p.solve()
b = p.get_values(b)
print [v for v,i in b.items() if i]
Bipartite Set
Partition the graph into two independent sets
p = MixedIntegerLinearProgram()
b = p.new_variable(binary = True)

for u,v in g.edges(labels = False):
    p.add_constraint( b[u] + b[v] == 1 )

p.solve()
b = p.get_values(b)
print [v for v,i in b.items() if i]
print [v for v,i in b.items() if not i]
Distances
Compute the distance from vertex 0 to any other
p = MixedIntegerLinearProgram()
d = p.new_variable()
p.set_objective(sum([d[v] for v in g]))

p.add_constraint( d[0] == 0 )
for u,v in g.edges(labels = False):
    p.add_constraint( -1 <= d[u] - d[v] <= 1 )

p.solve()
print p.get_values(d)
Girth
Size of the shortest cycle
p = MixedIntegerLinearProgram(maximization = False)
b = p.new_variable(binary = True)
p.set_objective(sum([b[v] for v in g]))
p.add_constraint(sum([b[v] for v in g]) >= 1)

for v in g:
    edges = g.edges_incident(v, labels = False)
    p.add_constraint( sum([b[Set(e)] for e in edges]) == 2*b[v] )

p.solve()
b = p.get_values(b)
print [v for v in g if b[v]]
Matching
Maximum number of non-incident edges
p = MixedIntegerLinearProgram(maximization = True)
b = p.new_variable(binary = True)
p.set_objective(sum([b[Set(e)] for e in g.edges(labels = False)]))

for v in g:
    edges = g.edges_incident(v, labels = False)
    p.add_constraint( sum([b[Set(e)] for e in edges]) <= 1 )

p.solve()
b = p.get_values(b)
print [e for e,i in b.items() if i]
Partition
Partition a set of integers into two sets whose sum is equal
l = [82, 61, 56, 44, 28, 87, 90, 36, 11, 48, 9]
p = MixedIntegerLinearProgram()
b = p.new_variable(binary = True)
p.add_constraint(p.sum([ v*b[v] for v in l ]) == sum(l)/2)
p.solve()
b = p.get_values(b)
print [v for v in b if b[v] == 1]
Subset Sum
Find a nonempty subset of integers with null sum
l = [28, 10, -89, 69, 42, -37, 76, 78, -40, 92, -93, 45]
p = MixedIntegerLinearProgram()
b = p.new_variable(binary = True)
p.add_constraint(p.sum([ v*b[v] for v in l ]) == 0)
p.add_constraint(p.sum([ b[v] for v in l ]) >= 1)
p.solve()
b = p.get_values(b)
print [v for v in b if b[v] == 1]
Feedback Arc Set
Minimum set of arcs hitting all circuits
p = MixedIntegerLinearProgram(maximization = False)
b = p.new_variable(binary = True)
p.set_objective(sum([b[u,v] for u,v in g.edges(labels = False)]))
p.solve()
while True:
    b_sol = p.get_values(b)
    g_tmp = DiGraph()
    g_tmp.add_edges([e for e,i in b_sol.items() if i==0])
    isok, C = g_tmp.is_directed_acyclic(certificate = True)
    if isok:
       break
    edges = zip(C, C[1:]+[C[0]])
    p.add_constraint(sum([b[e] for e in edges])>= 1)
    p.solve()
print [e for e,i in b_sol.items() if i==1]
Feedback Vertex Set
Minimum set of vertices hitting all circuits
p = MixedIntegerLinearProgram(maximization = False)
b = p.new_variable(binary = True)
p.set_objective(sum([b[v] for v in g]))
p.solve()
while True:
    b_sol = p.get_values(b)
    vertices = [v for v,i in b_sol.items() if i==0]
    g_tmp = g.subgraph(vertices = vertices)
    isok, C = g_tmp.is_directed_acyclic(certificate = True)
    if isok:
       break
    p.add_constraint(sum([b[v] for v in C])>= 1)
    p.solve()
print [e for e,i in b_sol.items() if i==1]
Hamiltonian Cycle
A cycle going through all vertices
p = MixedIntegerLinearProgram()
b = p.new_variable(binary = True)
for v in g:
    edges = g.edges_incident(v, labels = False)
    p.add_constraint( sum(b[Set(e)] for e in edges) == 2)
p.solve()
while True:
    b_sol = p.get_values(b)
    edges = [e for e,i in b_sol.items() if i == 1]
    g_tmp = g.subgraph(vertices = g.vertices(), edges = edges)
    cc = g_tmp.connected_components()
    if len(cc) == 1:
       break
    boundary = g.edge_boundary(cc[0], labels = False)
    p.add_constraint(sum([b[Set(e)] for e in boundary])>= 2)
    p.solve()

print g_tmp.edges(labels = False)
3-coloration
Partition a graph into three independent sets
p = MixedIntegerLinearProgram()
b = p.new_variable(binary = True)
for v in g:
    p.add_constraint( b[v,0] + b[v,1] + b[v,2] == 1 )

for u,v in g.edges(labels = False):
    p.add_constraint( b[u,0] + b[v,0] <= 1 )
    p.add_constraint( b[u,1] + b[v,1] <= 1 )
    p.add_constraint( b[u,2] + b[v,2] <= 1 )

p.solve()
b = p.get_values(b)
print [v for (v,c),i in b.items() if i and c == 0]
print [v for (v,c),i in b.items() if i and c == 1]
print [v for (v,c),i in b.items() if i and c == 2]