ILP MDS (Minimum Dominating Set)를위한 Python 모델링

Question

MDS 문제 를 해결하기위한 코드를 작성 중 입니다. 문제는 다음과 같습니다.\begin{align}\min&\quad\sum_{v\in V}y_v\\\text{s.t.}&\quad y_v+\sum_{(u,v)\in E}y_u\ge1\quad\forall v\in V\\&\quad y_v\in\{0,1\}\quad\forall v\in V.\end{align}

Python에서 Pulp 및 nx.network 를 사용 하여 다음과 같이 문제를 모델링했습니다.

• 문제 prob = pulp.LpProblem("MinimumDominatingSet", pulp.LpMinimize)
• 변수 y = pulp.LpVariable.dicts("y", g.nodes(), cat=pulp.LpBinary)
• 목표 for (v,u) in g.edges(): prob += pulp.lpSum(y)
• 강제 for (v,u) in g.edges(): prob += y.get(v) + sum(y.get(u) for (v,u) in g.edges) >= 1

간단한 별 모양으로 출력을 테스트 해 보았습니다. 불행히도 출력이 올바르지 않습니다. 제약 조건을 모델링하는 데 문제가있을 수 있다고 생각합니다.

누구든지 이것을 통해 나를 안내 할 수 있습니까?

Answer 1

목표는이어야하며 prob+= pulp.lpSum(y)제약 조건은 다음과 같아야합니다.

for v in g.nodes():
       prob += y[v] + pulp.lpSum([y[u] for u in g.neighbors(v)]) >= 1