1
$\begingroup$

I am attempting to capture the nature of a "source" node as well as a "sink" node where the net flow for each node aside from the source and sink is zero. Here is my code so far:

import gurobipy as gp
from gurobipy import GRB
import pandas
import os


# writes constraints and objective to model file for easier inspection
def write_to_file(model, filestring):
    directory = os.getcwd()
    filename = directory+filestring
    if model.write(filename):
        return 0
    else:
        print("failed to write to file")
        return -1

# nodes
# for my example, SOURCE s = 2 and SINK t = 7
vertices = [1,2,3,4,5,6,7]

# arcs = edges, each arc has a fixed capacity
arcs, capacity = gp.multidict({
    (2,1) : 100,
    (2,3) : 50,
    (3,4) : 25,
    (4,7) : 25,
    (3,6) : 200,
    (1,6) : 500,
    (3,7) : 25,
    (6,5) : 500,
    (6,7) : 50,
    (5,7) : 200
})

# create model
m = gp.Model("Maximum Flow Problem")

# define variables
flow = m.addVars(arcs, name = "flow")

# flow capacity
m.addConstrs(
    (flow.sum(i,j) <= capacity[i,j] for i,j in arcs), "cap")

# flow conservation ISSUE HERE!
m.addConstrs(
    (flow.sum('*',j) - flow.sum(j,'*') == 0 for j in vertices), "node")

obj = (flow.sum('*', 7) - flow.sum(7,'*'))
m.setObjective(obj, GRB.MAXIMIZE)

#write_to_file(m, "\\rec2_model_simple.lp")

m.optimize()

The issue has to do with the flow conservation constraint. I want to ensure all flow going in and out of all nodes that aren't s=2 and t=7 to equal zero; however, I do not know how to capture this in my constraint.

I would like to have something like:

m.addConstrs(
    (flow.sum('*',j) - flow.sum(j,'*') == 0 for j != 2 or j != 7 in vertices), "node")

This throws an error, but I am curious if there is something similar in nature to capture this notion of a "source" and a "sink" in my flow conservation constraint. This may be a question more geared towards the python language instead of gurobipy, but since it is a question specific to modeling, I felt as though it is appropriate here.

$\endgroup$

1 Answer 1

2
$\begingroup$

One way to model this is to add a dummy arc from the sink to the source and impose flow balance of 0 at every node, including the source and sink.

But if you prefer the conditional constraint, I think the proper syntax is:

m.addConstrs(
    (flow.sum('*',j) - flow.sum(j,'*') == 0 for j in vertices if j != 2 and j != 7), "node")
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.