MILP Ensemble minimum Codage de couverture Vertex par Python ou MATLAB?

Question

En guise de suivi de ma question pour modéliser un simple moded du problème de couverture de vertex d'ensemble minimum, qui est montré ci-dessous. J'aimerais avoir votre aide pour modéliser ce problème en utilisant Python ou MATLAB. Je crois que chaque arête avec son sommet d'origine et son sommet de destination en tant que variable binaire résoudra le problème. Je ne sais pas comment cette variable représentera les deux sommets.
Le problème peut être représenté sous forme de graphique$G=(V,E)$ où nous voulons: $$ \min \quad \sum_{v\in V} x_v $$ sujet à \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

En Python, avec pulp et 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)

Je vous suggère

1. Consultez les exemples de pulp pour comprendre la syntaxe
2. Ne vous contentez pas de copier-coller la réponse ci-dessus si vous voulez apprendre quelque chose