ILP最小支配集合（MDS）の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