Sum of links neighbors in a graph

Question

I'm trying to model this constraint in an optimization problem using Pulp and NetworkX. Here is a piece of code I'm using.

import pulp 
import networkx as nx

g = nx.Graph() 

links = [(1,2),(1,4),(1,5),(2,5),(2,3),(3,5),(3,4),(4,5)] 

g.add_edges_from(links)

#The problem
prob = pulp.LpProblem("MinimumSetVertexCover", pulp.LpMinimize)

# The variables
y = pulp.LpVariable.dicts("y", g.nodes(), cat=pulp.LpBinary)
z = pulp.LpVariable.dicts("z", g.edges(), cat=pulp.LpBinary)

#The objective function

for (u,v) in g.edges():
    prob += pulp.lpSum(y) + pulp.lpSum(z)

#The constraints
for (u,v) in g.edges():
    prob += z[(u,v)] <= y[v]
    prob += z[(u,v)] <= 1-y[u]
for v in g.nodes():
    prob +=  pulp.lpSum([z[(u,v)] for v in g.neighbors(u)]) >= 2*(1-y[v])    

prob.solve()

The optimizer throws this error ---> 55 prob += pulp.lpSum([z[(u,v)] for v in g.neighbors(u)]) >= 2*(1-y[v]) KeyError: (5, 1)

Any help will be very appreciated.

Answer 1

This is because you are trying to call z[(5,1)], while your variable is z[(1,5)]. Also u and v are mixed up in the last constraint.

You can try:

for v in g.nodes():
    prob +=  pulp.lpSum([z[(u,v)] for u in g.neighbors(v) if (u,v) in z]) + pulp.lpSum([z[(v,u)] for u in g.neighbors(v) if (v,u) in z]) >= 2*(1-y[v])