MILP Set minimum pengkodean penutup Vertex oleh Python atau MATLAB?

Question

Sebagai tindak lanjut untuk pertanyaan saya untuk pemodelan sederhana moded dari masalah penutup simpul set minimum, yang ditampilkan berikutnya. Saya ingin mendapatkan bantuan Anda dalam memodelkan masalah ini menggunakan Python atau MATLAB. Saya percaya bahwa setiap tepi dengan simpul asal dan simpul tujuan sebagai variabel biner akan menyelesaikan masalah. Saya sedikit bingung tentang bagaimana variabel ini akan mewakili kedua simpul.
Masalahnya bisa ditampilkan sebagai grafik$G=(V,E)$ dimana kami ingin: $$ \min \quad \sum_{v\in V} x_v $$ tunduk pada \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

Dengan Python, dengan pulp dan 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)

saya menyarankan Anda

1. Lihat contoh pulp untuk memahami sintaksnya
2. Jangan hanya copy paste jawaban di atas jika ingin mempelajari sesuatu