python - Transportation problem with additional constraints

Question

I am trying to implement a transportation problem using PuLP package. In my case, its a slightly modified and has additional constraints. Lets say there are 7 suppliers [s1,s2,s3,s4,s5,s6,s7] and 6 destinations [d1,d2,d3,d4,d5,d6]. Demand for every destination is 1. supply is for each supplier is 3.

So far the implementation:

capacity=3
suppliers,targets = cost.shape
    objective = LpProblem("Optimize_allocation",LpMinimize)
    x = LpVariable.dicts("assignment", product(range(suppliers), range(targets)), 0, 1)
    objective += lpSum(cost[i, j] * x[i, j] for i in range(suppliers) for j in range(targets))
    
    for j in range(targets):
        condition1 = lpSum( x[i, j] for i in range(suppliers)) == 1
        objective+= condition1
    for i in range(suppliers):
        condition2 = lpSum(x[i, j] for j in range(targets)) <= capacity
        objective+= condition2  
    
    objective.solve(PULP_CBC_CMD(msg=0))

Additional constraints I have are, destinations (d3,d4) will only accept goods from only one supplier(could be any one of those) and this supplier should only serve them and not serve to any other destinations. If I combine them to one destination with demand 2 and average the cost that would work but how do I ensure the later part of the constraint? This is just an example case but in my actual problem, there could be multiple destinations that group among themselves and demand the same constraint example: (d1,d2) and (d5,d6,d3).

EDIT: Updated to the following working code based on @kabdulla's answer but the last constraint is changed.

suppliers = 10
targets = ['A','B','C','D','E','F','G','H','I']
grps = [['A','B','C'],['D'],['E'],['F','G'],['H','I']] #constraint groups
groups = [[0, 1, 2], [3], [4], [5, 6], [7, 8]] #constraint group ids
capacities = [3, 1, 1, 2, 2]
capacity = 3
cost = np.random.rand(suppliers,len(targets))
objective = LpProblem("Optimize_allocation",LpMinimize)
x = LpVariable.dicts("assignment1", product(range(suppliers), range(len(targets))), 0, 1,'Integer')
y = LpVariable.dicts("assignment2", product(range(suppliers), range(len(groups))), 0, 1,'Integer')
objective += lpSum(cost[i, j] * x[i, j] for i in range(suppliers) for j in range(len(targets)))

    
for j in range(len(targets)):
    objective+= lpSum( x[i, j] for i in range(suppliers)) == 1
     
    
for i in range(suppliers):
    objective+= lpSum(x[i, j] for j in range(len(targets))) <= capacity
     

for i in range(suppliers):
    for k in range(len(groups)):
        objective += lpSum(x[i,j] for j in groups[k]) <= y[i,k]*capacities[k]
        
    
for k in range(len(groups)):
    objective += lpSum(y[i,k] for i in range(suppliers)) == 1


for i in range(suppliers):
    objective+= lpSum(y[i, j] for j in range(len(groups))) <= 1

objective.solve()

question from:https://stackoverflow.com/questions/65850261/transportation-problem-with-additional-constraints

Answer 1

First an observation - your x[i, j] variables (qty to supply from supplier i to target j) are continuous - suggesting that a fraction of a unit can be shipped. If that's not the intention these x need to be made integer (cat='Integer' in call to LpVariable.dicts()).

If I understand your additional constraints correctly there exist some "exclusive supply" sets E_k of target nodes. Within one of these sets:

• All supply must come from a single supplier node
• That supplier must not provide to any node outside of the set

To enforce this kind of logic you are going to need some binary variables (if your x variables are non-continuous and limited to range [0,1] (i.e. they are binary) you might be able to use them directly). I'll assume your x are continuous as given.

One way to solve this would be to introduce new binary variables y[i, k] which are 1 iff supplier i is the chosen exclusive supplier to set k.

Assuming you had also declared a list-of-lists of target nodes which belong to the same exlusive supply sets E you could add required constraints something like this:

for i in suppliers:
    for k in range(len(E)):
        objective += lpSum(x[i,j] for j in E[k]) <= y[i, k]*M[k]

Where M[k] are sufficiently large that they don't add additional constraints when y[i,k] is 1 (for example this could just be the sum of demands of nodes in the kth exclusive supply set.

Then you can enforce required constraints on the y[i,k] variables - i.e. each set k must have only one supplier to it:

for k in range(len(E)):
    objective += lpSum(y[i, k] for i in suppliers) == 1

And finally you'd need to add the constraint that if supplier i is serving exclusive set k (i.e. y[i,k] == 1) that they are not allowed supply any nodes not in that set:

for i in suppliers:
    for k in range(len(E)):
        objective += lpSum(x[i, j] for j in targets if j not in E[k]) <= 
                       (1 - y[i,k])*N[k]

Where N[k] are sufficiently large that they don't add additional constraints when y[i,j] == 0 (for example could be the sum of demands of nodes not in the kth exclusive supply set.