CARI 2014 Extrait de 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] `````` 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] ``````