3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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
Improve this answer
$\endgroup$
2
  • 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, 2020 at 18:06
  • 2
    $\begingroup$ nx has simplified my life so many times ! pulp too in fact ! great tools $\endgroup$
    – Kuifje
    Nov 11, 2020 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.