Multi Knapsack Problem with conditional constraint

Answered

Thalles Morais

• September 24, 2021 16:05
• Edited

Hi, 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?

0

• 

  Maliheh Aramon

  Gurobi Staff

  • October 04, 2021 16:48
  • Edited

  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 higher-level 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
• 

  Maliheh Aramon

  Gurobi Staff

  • October 05, 2021 21:30

  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
• 

  Thalles Morais

  • October 04, 2021 16:47

  

  

  

  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
• 

  Maliheh Aramon

  Gurobi Staff

  • October 05, 2021 01:13

  Hello Thalles, 

  You would need to re-write 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"
  )

  The constraint c0 ensures that if item \(\texttt{i}\) is assigned to the current knapsack index, item \(\texttt{i2}\) will be assigned to a knapsack with a higher index. The constraint c0 takes care of the boundary case as well. If item 1 is assigned to the last knapsack, the constraint \(\texttt{x["item_1", "knapsack_3"] <= 0}\) is added to the model, enforcing item 1 cannot be assigned to the last knapsack. This makes sense because if item 1 is assigned to knapsack 3, items 4 and 5 must be assigned to a knapsack with a higher index which is impossible. Therefore, we cannot have a solution where item 1 is assigned to knapsack 3.
  
  Best regards,

  Maliheh

  0
• 

  Thalles Morais

  • October 05, 2021 12:04

  

  

  

  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/modeling-examples/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 18

  year_2: 1, 3, 5, 6 and 7

  year_3: 2

   

  And 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
• 

  Thalles Morais

  • October 06, 2021 16:31
  • Edited

  

  

  

  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.