Search code examples
pythonnetworkxgurobiinteger-programming

Trying to code summation of combination of nodes in a graph for gurobi optimization with quicksum

Im trying to code this into python using gurobi and networkx,

S >= quicksum(uij for j in N) for every i in N

My code is

import gurobipy as grb
import networkx as nx

g = nx.Graph()
g.add_edges_from(edges)

for i in g.nodes_iter():
     m.addConstr(S >= grb.quicksum(u[i,j] for j in g.nodes_iter()))

The problem is that I get Key Error (1,1) which makes sense cuz I dont have the edge (1,1)

But I do want to sum for every i in the node, the summation of all the uij for all j that is connected to the particular node i.

This is not a degree question it is actually summing up the connected component, so uij is 1 if there is a pathway between i and j. I have coded this as a Critical Node Detection Problem.

Please help! Thanks!

Solution

  • You want the sum to be just over the nodes in the graph. networkx has a method neighbors_iter that will do just that

    for i in g.nodes_iter():
 m.addConstr(S >= grb.quicksum(u[i,j] for j in g.neighbors_iter(i)))

    In any case, you should avoid iterating across all pairs of nodes unless you are only working with very dense graphs.