MILP 최소 세트 Vertex Cover Coding by Python 또는 MATLAB?

Question

다음에 표시되는 최소 세트 정점 커버 문제의 단순 모드 모델링에 대한 내 질문에 대한 후속 조치입니다. Python 또는 MATLAB을 사용하여이 문제를 모델링하는 데 도움을 받고 싶습니다. 원점 정점과 대상 정점을 이진 변수로 사용하는 각 모서리가 문제를 해결할 것이라고 생각합니다. 이 변수가 두 정점을 어떻게 표현하는지에 대해 약간 혼란 스럽습니다.
문제는 그래프로 표시 될 수 있습니다.$G=(V,E)$ 우리가 원하는 곳 : $$ \min \quad \sum_{v\in V} x_v $$ 대상 \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에서 pulp 및 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)

하는거 어때

1. 구문을 이해하려면 pulp의 예 를 확인하세요.
2. 무언가를 배우고 싶다면 위의 답변을 복사하지 마십시오.