| 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]
# Note: viewed as a boolean, 0 is False and 1.0 is True
|
| 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]
|
| 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]
|
| 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]
|
| 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]
|
| 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]
|
| 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]
|
| GCD |
| The gcd of a list L of integers |
gcd([12,15,30]) = 3 |
Minimize the sum of the L[i] * u[i], while staying >= 1 |
p = MixedIntegerLinearProgram(maximization=False)
u = p.new_variable(integer = True)
p.set_objective(sum(j*u[i] for i,j in enumerate(L)))
p.add_constraint(sum(j*u[i] for i,j in enumerate(L)) >= 1)
p.solve()
|
| Sudoku |
| Fill an incomplete Sudoku grid |
Get some instances of the Sudoku class and solve them, for example:
sage: S = Sudoku('\
....: 1....7.9.\
....: .3..2...8\
....: ..96..5..\
....: ..53..9..\
....: .1..8...2\
....: 6....4...\
....: 3......1.\
....: .4......7\
....: ..7...3..') ; S
+-----+-----+-----+
|1 | 7| 9 |
| 3 | 2 | 8|
| 9|6 |5 |
+-----+-----+-----+
| 5|3 |9 |
| 1 | 8 | 2|
|6 | 4| |
+-----+-----+-----+
|3 | | 1 |
| 4 | | 7|
| 7| |3 |
+-----+-----+-----+
sage: sudoku_solve_milp(S)
+-----+-----+-----+
|1 6 2|8 5 7|4 9 3|
|5 3 4|1 2 9|6 7 8|
|7 8 9|6 4 3|5 2 1|
+-----+-----+-----+
|4 7 5|3 1 2|9 8 6|
|9 1 3|5 8 6|7 4 2|
|6 2 8|7 9 4|1 3 5|
+-----+-----+-----+
|3 5 6|4 7 8|2 1 9|
|2 4 1|9 3 5|8 6 7|
|8 9 7|2 6 1|3 5 4|
+-----+-----+-----+
|
|
You can get an possible solution on this file.
|