How to define constraints over multiple dimensions?

Answered

Irene Alisjahbana

• July 14, 2020 23:13

Hello, 

I am new to Gurobi and would like to model a simple resource allocation problem. I have looked at the example Jupyter notebooks on Github but I am still having trouble defining the constraints. Suppose this is (part of) the problem I would like to solve: 

Where I is the set of supply nodes, J is the set of resource types, and L is the set of demand nodes. I would like to minimize the total deployment time, t_ijl, which is the time it takes resource type j to be transported from supply node i to demand node l. q_jl is the quantity of resource type j that demand node l needs, and a_ij is the available resource j at supply node i. 

I have input the data as follows:

resource = ['A', 'B', 'C']
demand_node = ['Sink1', 'Sink2']
supply_node = ['Node1', 'Node2', 'Node3']

for q_jl:

demand_combo, demand_quantity = gp.multidict({
('A','Sink1') : 2,
('A','Sink2') : 2,
('B','Sink1') : 2,
('B','Sink2') : 1, 
('C','Sink1') : 3,
('C','Sink2') : 3
})

for a_ij:

resource_combo, supply_avail = gp.multidict({
('Node1', 'A') : 2,
('Node2', 'A') : 1,
('Node3', 'A') : 1,
('Node1','B') : 1,
('Node2','B') : 1,
('Node3','B') : 0,
('Node1', 'C') : 1,
('Node2', 'C') : 1,
('Node3', 'C') : 1,
})

for t_ijl:

combinations, time = gp.multidict(
{('Node1','A', 'Sink1'): 1,
('Node2','A', 'Sink1'): 3,
('Node3','A', 'Sink1'): 5,
('Node1','A', 'Sink2'): 2,
('Node2','A', 'Sink2'): 3,
('Node3','A', 'Sink2'): 2,
('Node1','B', 'Sink1'): 3,
('Node2','B', 'Sink1'): 5,
('Node3','B', 'Sink1'): 0,
('Node1','B', 'Sink2'): 4,
('Node2','B', 'Sink2'): 5,
('Node3','B', 'Sink2'): 0,
('Node1','C', 'Sink1'): 8,
('Node2','C', 'Sink1'): 10,
('Node3','C', 'Sink1'): 9,
('Node1','C', 'Sink2'): 10,
('Node2','C', 'Sink2'): 10,
('Node3','C', 'Sink2'): 6
})

Then, for my decision variable, I defined the following:

x = m.addVars(combinations, vtype=GRB.BINARY, name = 'allocate')

I tried to do the following for the first constraint:

# capacity constraint
capacity = m.addConstr((x.sum('*', j, l) <= supply_avail[i,j] for i in supply_node for j in resource), name = 'capacity')

But it is giving me an error. I am sure that I am not correctly defining the constraint, but I am not sure how to fix it.

Also, is there a faster way to define my data? Should I be using some sort of list comprehension or pandas dataframe?

Any help would be greatly appreciated! Thank you. 

 

0

• 

  Eli Towle

  Gurobi Staff

  • July 15, 2020 00:49
  • Edited

  Hi Irene,

  It looks like to me like the first and second constraints are mixed up in the capacity constraint you coded. In particular, \( \texttt{supply_avail[i, j]} \) corresponds to \( a_{ij} \) in the formulation, which shows up in the second constraint set. However, you sum over \( I \) on the left-hand side, which is done only in the first constraint set. I'll assume we are trying to write the second constraint set.

  Model.addConstr() is used to add a single constraint. Instead, we can use Model.addConstrs() to add multiple constraints with a single method call. Additionally, for the second constraint, we want to sum over \( L \) on the left-hand side, not \( I \). Altogether:

  m.addConstrs((x.sum(i, j, '*') <= supply_avail[i, j] for i in supply_node for j in resource), name='capacity')

  This code adds the following constraints:

  capacity[Node1,A]: allocate[Node1,A,Sink1] + allocate[Node1,A,Sink2] <= 2                                                 
  capacity[Node1,B]: allocate[Node1,B,Sink1] + allocate[Node1,B,Sink2] <= 1                                                 
  capacity[Node1,C]: allocate[Node1,C,Sink1] + allocate[Node1,C,Sink2] <= 1                                                 
  capacity[Node2,A]: allocate[Node2,A,Sink1] + allocate[Node2,A,Sink2] <= 1                                                 
  capacity[Node2,B]: allocate[Node2,B,Sink1] + allocate[Node2,B,Sink2] <= 1                                                 
  capacity[Node2,C]: allocate[Node2,C,Sink1] + allocate[Node2,C,Sink2] <= 1                                                 
  capacity[Node3,A]: allocate[Node3,A,Sink1] + allocate[Node3,A,Sink2] <= 1                                                 
  capacity[Node3,B]: allocate[Node3,B,Sink1] + allocate[Node3,B,Sink2] <= 0                                                 
  capacity[Node3,C]: allocate[Node3,C,Sink1] + allocate[Node3,C,Sink2] <= 1 

  As far as a better way to define the data: explicitly defining the data in the code should be very fast. The model-building time should be negligible for a model of this size.

  Thanks,

  Eli

  0
• 

  Irene Alisjahbana

  • July 15, 2020 01:29

  

  

  

  Hi Eli, 

  Thank you for your quick reply.

  Apologies for the error. You are correct, I was trying to demonstrate the second set of constraints. 

  This makes a lot of sense and is exactly what I was looking for! Thank you.

  Best,

  Irene

  0

Please sign in to leave a comment.