MILP Minimo set Vertex cover coding da Python o MATLAB?

Question

In seguito alla mia domanda per la modellazione di un semplice problema di copertura del vertice del set minimo modificato, che viene mostrato di seguito. Mi piacerebbe avere il tuo aiuto per modellare questo problema usando Python o MATLAB. Credo che ogni bordo con il suo vertice di origine e vertice di destinazione come variabile binaria risolverà il problema. Sono un po 'confuso su come questa variabile rappresenterà entrambi i vertici.
Il problema può essere mostrato come grafico$G=(V,E)$ dove vogliamo: $$ \min \quad \sum_{v\in V} x_v $$ soggetto a \begin{align} x_u + x_v &\ge 1 \quad &\forall (u,v) \in E \\ \sum_{(u,v)\in E} z_{uv} &\ge k \\ z_{uv} &\le x_v \quad &\forall (u,v) \in E\\ z_{uv} &\le 1-x_u \quad &\forall (u,v) \in E\\ x_v&\in \{0,1\} \quad &\forall v \in V\\ z_{uv} &\in \{0,1\}\quad &\forall (u,v) \in E \end{align}

Answer 1

In Python, con pulp e networkx :

import pulp 
import networkx as nx

G = nx.Graph()
# define your graph here
#...


# define the problem
prob = pulp.LpProblem("MinimumSetVertexCover", pulp.LpMinimize)

# define the variables
x = pulp.LpVariable.dicts("x", G.nodes(), cat=pulp.LpBinary)
z = pulp.LpVariable.dicts("z", G.edges(), cat=pulp.LpBinary)

# define the objective function
prob += pulp.lpSum(x)

# define the constraints
for (u,v) in G.edges():
    prob += x[u] + x[v] >= 1
    prob += z[(u,v)] <= x[v]
    prob += z[(u,v)] <= 1-x[u]
prob += pulp.lpSum(z) >= k

# solve
prob.solve()

# display objective function value
print("number of vertices in solution : %s"%pulp.prob.objective.value())

# display solution
for v in G.nodes():
    if pulp.value(x[v]) > 0.9:
         print("node %s selected"%v)

ti suggerisco

1. Dai un'occhiata agli esempi di pulp per capire la sintassi
2. Non limitarti a copiare e incollare la risposta sopra se vuoi imparare qualcosa