I'm writing a code for solving the MDS problem, the problem is: \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}
I have used Pulp and nx.network in python to model the problem as following:
- The problem
prob = pulp.LpProblem("MinimumDominatingSet", pulp.LpMinimize)
- Variables
y = pulp.LpVariable.dicts("y", g.nodes(), cat=pulp.LpBinary)
- The objective
for (v,u) in g.edges(): prob += pulp.lpSum(y)
- Constraint
for (v,u) in g.edges(): prob += y.get(v) + sum(y.get(u) for (v,u) in g.edges) >= 1
I have tried to test the output with a simple star figure. Unfortunately, the output is not correct. I'm suspecting there may be an issue with modeling the constraint.
Could anyone guide me through this?