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():
       prob += y[v] + pulp.lpSum([y[u] for u in g.neighbors(v)]) >= 1
  • 1
    $\begingroup$ I really appreciate your help. thank you so much. I didn't know that nx.network class has the neighbors' attribute. $\endgroup$ – Amedeo Nov 11 '20 at 18:06
  • 2
    $\begingroup$ nx has simplified my life so many times ! pulp too in fact ! great tools $\endgroup$ – Kuifje Nov 11 '20 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.