3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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]) 
$\endgroup$
5
  • $\begingroup$ Thank you for your reply. but this repeats the same output for the whole set of nodes. while the neighbors of a node should be different from the other nodes $\endgroup$
    – Amedeo
    Nov 12 '20 at 13:57
  • $\begingroup$ You mean the same error is thrown ? Can you show the exact error ? Try the above code that I have edited. $\endgroup$
    – Kuifje
    Nov 12 '20 at 14:17
  • $\begingroup$ No, It does not throw an error but the output is out of logic _C17: 2 x_1 + z_(1,_5) + z_(2,_5) + z_(4,_5) + z_(5,_3) >= 2 _C18: 2 x_2 + z_(1,_5) + z_(2,_5) + z_(4,_5) + z_(5,_3) >= 2 _C19: 2 x_4 + z_(1,_5) + z_(2,_5) + z_(4,_5) + z_(5,_3) >= 2 _C20: 2 x_5 + z_(1,_5) + z_(2,_5) + z_(4,_5) + z_(5,_3) >= 2 _C21: 2 x_3 + z_(1,_5) + z_(2,_5) + z_(4,_5) + z_(5,_3) >= 2 It is the same constraint for every node. $\endgroup$
    – Amedeo
    Nov 12 '20 at 14:20
  • $\begingroup$ $u$ and $v$ were mixed up. Retry the exact code in the answer $\endgroup$
    – Kuifje
    Nov 12 '20 at 14:25
  • $\begingroup$ Thank you so much @ Kuifje, this solves the error. $\endgroup$
    – Amedeo
    Nov 12 '20 at 16:26

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.