CARI 2014 Extrait de la page de Nathann COHEN

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 )

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
Vertex Cover
Minimum Set of vertices touching each edge
Partition a set of integers into two sets whose sum is equal
Bipartite Set
Partition the graph into two independent sets
Subset Sum
Find a nonempty subset of integers with null sum
Compute the distance from vertex 0 to any other
Size of the shortest cycle
Maximum number of non-incident edges
Feedback Arc Set
Minimum set of arcs hitting all circuits
Feedback Vertex Set
Minimum set of vertices hitting all circuits
Hamiltonian Cycle
A cycle going through all vertices
Partition a graph into three independent sets