MILP answers D'après la page de Nathann COHEN
http://steinertriples.fr/ncohen/tut/LP_examples/

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]

# 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.