Multi Knapsack Problem with conditional constraint
AnsweredHi, My name is Thalles and I'm working on the multi knapsack problem, where I have i items (eachone with their weights) and j knapsacks (each one with their capacities), and my goal is to generate a solution where I get the maximum value of values in the somatory of knapsacks. Until here my code works fine, as we can see below:
values = {item_1: 40, item_2: 35, item_3: 30, item_4: 25, item_5: 20, item_6: 15, item_7: 10}
weights = {item_1: 12, item_2: 17, item_3: 31, item_4: 44, item_5: 49, item_6: 67, item_7: 81}
capacities = {knapsack_1: 100, knapsack_2: 200, knapsack_3: 150)
# This values above are just exemples, my data is too bigger than them so I just simplified what I want to say #
m.gp.Model()
# Insert the decision variables
x = m.addVars(items, knapsacks, vtype = gp.GRB.BINARY)
# Define the objective function
m.setObjective(gp.quicksum(x[i, j] * values[i] for i in items for j in knapsacks), sense=gp.GRB.MAXIMIZE)
# Constraint 1
c1 = m.addConstrs(gp.quicksum(x[i,j] for j in knapsacks) <= 1 for i in items)
# Constraint 2
c2 = m.addConstrs(gp.quicksum(x[i,j] * weights[i] for i in items) <= capacities[j] for j in knapsacks)
# Run the model
m.optimize()
What I want to do now is insert a conditional constraint where, for exemple, if item 1 is on the solution, item 4 and item 5 must be too. I've created a dict that shows this relationship:
rel, val = gp.multidict({
(item_1, item_4) : 1
(item_1, item_5) : 1
})
# And it goes for the another items condition. #
So, I've tried to run this follow codes:
c0 = m.addConstrs(( x[i, j] <= x[i2, j] for i, i2 in rel), name = 'c0')
# Doesn't work
c0 = m.addConstrs(( x[i, j] <= x[i2, j] for i, i2 in rel for j in knapsacks), name = 'c0')
# Doesn't work either
Any sugestions?

Hi Thalles,
I do not see in your code snippet how you are defining \(\texttt{items}\) and \(\texttt{knapsacks}\) variables. I am assuming that they are lists of item and knapsack strings.
We need to first clarify one point. If item 1 is assigned to knapsack 1, do you need to ensure items 4 and 5 are assigned to the same knapsack? Or is it acceptable for items 4 and 5 to be assigned to another knapsack?Your latter constraint version, copied below, ensures that if items 1 is assigned to knapsack \(\texttt{j}\), items 4 and 5 are also assigned to the same knapsack \(\texttt{j}\).
c0 = m.addConstrs(
(x[i, j] <= x[i2, j] for i, i2 in rel for j in knapsacks), name="c0"
)
If you are looking for the more relaxed version, you need the following which ensures if item 1 is selected, items 4 and 5 are also selected, regardless of the knapsack id assigned to each.c0 = m.addConstrs((x.sum(i, "*") <= x.sum(i2, "*") for i, i2 in rel), name="c0")
On a different but important note, I would like to mention that our Python interface has higherlevel constructs that allow building models using a more mathematical syntax. For example, instead of calling quicksum, we can directly call the sum method on the tupledict x. I recommend checking the example netflow.py to learn more about the syntax.1 
Hello, Maliheh!
Thank you so much for your reponse!
The second code you mentioned helped me a lot! But unfortunetly the solution doesn't consider a order to put the values in the years. Items 4 and 5 can be in the solution in diferents knapsacks than item 1 but item 1 must come first, in a previous knapsack. The solution puts item 1 in the knapsack 3, and items 4 and 5 in the knapsack 2, it can't happen, any thought?
Thanks again for your support!
0 
Hello Thalles,
You would need to rewrite the constraint to ensure that if item 1 is assigned, items 4 and 5 must be assigned to a knapsack with a higher index value.
Continuing with your notation where \(\texttt{items}\) and \(\texttt{knapsacks}\) are list of strings, we will have:
c0 = m.addConstrs(
(
x[i, current_knapsack]
<= gp.quicksum(
x[i2, next_knapsack] for next_knapsack in knapsacks[current_index + 1 :]
)
for i, i2 in rel
for current_index, current_knapsack in enumerate(knapsacks)
),
name="c0"
)
Best regards,Maliheh0 
Hi Maliheh!
Thanks again for your support! You are being very helpful!
I agree with you that this code make sense but the solution stil don't being what I expect with it. I found an gurobi example that is a little similar with my problem (https://colab.research.google.com/github/Gurobi/modelingexamples/blob/master/opencast_mining/opencast_mining_gcl.ipynb#scrollTo=LRuoYg59oXIu). I only created the parameter years on it:
years = [year_1, year_2, year_3] )
to insert on the variable extract:
extract = model.addVars(blocks, years, ub=1, vtype=GRB.BINARY, name="extract" )and the dict weights where all the blocks have the same weight 2.000, so I could to insert the constraints c1 and c2 from my notebook (on this case the limit for year is 10.000 weights).I'm mentioning this example because mine is too big to put here and this one simulates well what I want to do. Unfortunelly the result are being the same of my notebook, and when I run the c0 constraint you sugested the solution returns:year_1: 17 and 18year_2: 1, 3, 5, 6 and 7year_3: 2And I know that solution is not right.Thank you again for your support, Maliheh! If you have any ideas about it, I'll apreciate that! Anyway, you already being very helpeful.0 
Hi Thalles,
I think you are mapping the blocks and the years to the items and knapsacks, respectively. In the solution you shared, we have x[1, 2] = 1 and x[5, 2] = 1 meaning that both items 1 and 5 are assigned to knapsack 2. Using c0, we should have already added the constraint: x[1, 2] <= x[5, 3]. This means if x[1, 2] = 1, x[5, 3] must be 1. Since you also have x[5, 1] + x[5, 2], x[5, 3] <= 1 ( c1), you cannot have x[5, 2] = 1 in a feasible solution. Are you sure that you have coded the constraints correctly? I would suggest to write your model in an LP format and look at the constraints added to ensure that your program adds all the constraints it should add.Best regards,
Maliheh
1 
Hello Maliheh!
The solution I shared was following the constraints of the example, not the constraints of my model. In that gurobi example the block 5 is not dependent of block 1, but block 17 is. I shared this example just to be easier to undertand what I'm doing.
Anyway, after analyse the code c0 you shared I realized that changing the:
[current_index + 1 :] to [current_index  3 :]
and inverting the order of the knapsacks, changing:
knapsacks = [knapsack_1, knapsack_2, knapsack_3] to knapsacks = [knapsack_3, knapsack_2, knapsack_1]
The solution works fine.
So thank you so much for your help! You took off a giant piano from my shoulders!
0
Please sign in to leave a comment.
Comments
6 comments