3
$\begingroup$

I'm trying to model a constraint in Python using Pulp and networkX that is getting the sum of the edges that contain this node over all the nodes. The constraint can be like that: $$\sum_{m\in\cal N}z_{(m,n)}\succeq k(1-y_m),\quad\forall m\in\cal N.$$

I have used this code to model the constraint:

for m in g.nodes(): prob += pulp.lpSum(z[(m,n)] for m in g.nodes()) >= k*(1-y[m])

This piece of code rises an error about the key of the dictionary since the variable dictionary $z$ doesn't contains all the neighbors values. If I used this instead

for m in g.nodes(): prob += pulp.lpSum(z[(m,n)] for (u,v) in g.edges()) >= k*(1-y[m])

It sums all the links, not the ones associated with link $m$.

I would like your help with this!.

Please be noted that $z_{(m,n)}$ is a dict of the graph edges

$\endgroup$
4
$\begingroup$

Alternatively, just like in your previous question :

for m in g.nodes():
    prob += pulp.lpSum(z[(m,n)] for n in g.neighbors(m)) >= k*(1-y[m])
$\endgroup$
3
  • $\begingroup$ Thank you @Kuifje. I have tried this actually before asking but it throws an error about the key of the dict. For example, If I have this small set of edges [ [(1,2),(1,4),(1,5),(2,5),(2,3),(3,5),(3,4),(4,5)] ] The optimizer throws an error as KeyError: (2, 1). I think this is because the dict of Z which is the dict of edges doesn't contain the value of z_(2,1) $\endgroup$ – Amedeo Nov 12 '20 at 12:37
  • $\begingroup$ First, I think there is an extra set of brackets in your set of edges. This may be what triggrs the KeyError. Second, I suggest you post your full code in another question, so that we can see everything and help you with that. $\endgroup$ – Kuifje Nov 12 '20 at 13:16
  • $\begingroup$ Thank you for your reply. The extra brackets are not in the code, they are here by mistake. However, I will post another question. $\endgroup$ – Amedeo Nov 12 '20 at 13:21
2
$\begingroup$

You can use:

all_neighbors(graph, node): Returns all of the neighbors of a node in the graph.

function in networkX to find all the nodes which are connected to node m and then use the first constraint that you mentioned. I think there is a typo in the constraint as well instead of $m$ you should have $n$ (it's confusing). The output of that function is iterator you need to save it as a list (I am not sure about the format that PuLP accept).

$\endgroup$
2
  • $\begingroup$ Thank you for your reply @Ogzu. $\endgroup$ – Amedeo Nov 12 '20 at 12:41
  • 1
    $\begingroup$ @OguzToragay's comment is relevant : because of the typo, you got your $u$ and $v$ mixed up in the last constraint. $\endgroup$ – Kuifje Nov 12 '20 at 15:12

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.