# Python modeling for ILP Minimum Dominating Set (MDS)

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?

Your objective should be prob+= pulp.lpSum(y), and the constraints should be :
for v in g.nodes():