Modelado de Python para el conjunto mínimo dominante de ILP (MDS)

Question

Estoy escribiendo un código para resolver el problema de MDS , el problema es:\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}

He usado Pulp y nx.network en Python para modelar el problema de la siguiente manera:

• El problema prob = pulp.LpProblem("MinimumDominatingSet", pulp.LpMinimize)
• Variables y = pulp.LpVariable.dicts("y", g.nodes(), cat=pulp.LpBinary)
• El objetivo for (v,u) in g.edges(): prob += pulp.lpSum(y)
• Restricción for (v,u) in g.edges(): prob += y.get(v) + sum(y.get(u) for (v,u) in g.edges) >= 1

Intenté probar la salida con una figura de estrella simple. Desafortunadamente, el resultado no es correcto. Sospecho que puede haber un problema con el modelado de la restricción.

¿Alguien podría guiarme a través de esto?

Answer 1

Su objetivo debería ser prob+= pulp.lpSum(y), y las limitaciones deberían ser:

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