Modélisation Python pour ILP Minimum Dominating Set (MDS)

Question

J'écris un code pour résoudre le problème MDS , le problème est:\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}

J'ai utilisé Pulp et nx.network en python pour modéliser le problème comme suit:

• Le problème prob = pulp.LpProblem("MinimumDominatingSet", pulp.LpMinimize)
• Variables y = pulp.LpVariable.dicts("y", g.nodes(), cat=pulp.LpBinary)
• L'objectif for (v,u) in g.edges(): prob += pulp.lpSum(y)
• Contrainte for (v,u) in g.edges(): prob += y.get(v) + sum(y.get(u) for (v,u) in g.edges) >= 1

J'ai essayé de tester la sortie avec une simple étoile. Malheureusement, la sortie n'est pas correcte. Je soupçonne qu'il peut y avoir un problème avec la modélisation de la contrainte.

Quelqu'un pourrait-il me guider à travers cela?

Answer 1

Votre objectif doit être prob+= pulp.lpSum(y), et les contraintes doivent être:

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