•  Gurobi Staff

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.
•    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?

•  Gurobi Staff

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
•    Hi Maliheh!

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.
•  Gurobi Staff

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

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