MILP Minimum Set Vertex Cover Codierung von Python oder MATLAB?

Question

Als Folge meiner Frage zur Modellierung eines einfachen Modells des Problems der minimalen Vertexabdeckung, das als nächstes gezeigt wird. Ich hätte gerne Ihre Hilfe bei der Modellierung dieses Problems mit Python oder MATLAB. Ich glaube, dass jede Kante mit ihrem Ursprungs- und Zielscheitelpunkt als binäre Variable das Problem lösen wird. Ich bin etwas verwirrt darüber, wie diese Variable beide Eckpunkte darstellt.
Das Problem kann als Grafik dargestellt werden$G=(V,E)$ wo wir wollen: $$ \min \quad \sum_{v\in V} x_v $$ vorbehaltlich \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 mit Pulp und 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)

ich schlage dich vor

1. Schauen Sie sich die Beispiele von Pulp an , um die Syntax zu verstehen
2. Kopieren Sie nicht einfach die obige Antwort und fügen Sie sie ein, wenn Sie etwas lernen möchten