MILP Minimum set Vertex kapak kodlaması Python veya MATLAB?

Question

Asgari ayarlı köşe örtüsü probleminin basit bir modülasyonunu modellemek için sorumu takiben, aşağıda gösterilen. Python veya MATLAB kullanarak bu problemi modellemede yardımınızı almak istiyorum. İkili değişken olarak başlangıç ​​noktası ve hedef köşesi olan her kenarın sorunu çözeceğine inanıyorum. Bu değişkenin her iki köşeyi nasıl temsil edeceği konusunda biraz kafam karıştı.
Sorun grafik olarak gösterilebilir$G=(V,E)$ istediğimiz yer: $$ \min \quad \sum_{v\in V} x_v $$ tabi \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

Python'da pulp ve networkx ile :

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)

Sana öneririm

1. Sözdizimini anlamak için pulp'un örneklerine göz atın
2. Bir şey öğrenmek istiyorsanız yukarıdaki cevabı kopyalayıp yapıştırmayın