5

I am trying to create an LP problem which is like the knapsack problem but where there is a fixed bonus/penalty based on the number of items chosen.

  • There are 20 items to choose from with some weight between 1 to 20.
  • Knapsack can hold a total weight W=40
  • If only 1 item is chosen, there is a penalty of -3
  • If 2 items are chosen, there is a bonus of 2
  • If 3 items are chosen, there is a bonus of 1.5
  • If 4 items are chosen, there is a bonus of 6
  • If 5 or more items are chosen, there is a penalty of -4

While it seems like a simple problem, the bonus/penalties are constantly changing, and there are times that the bonus for 1 item is so high that it's the solution. My objective function is to maximize the total weight and the bonus/penalty associated with the number of items chosen.

I tried creating a Dictionary (call it dict) for my bonus/penalties and then having my objective function be sum(items[i]*weights[i] for i in 1:20) + dict[sum(items[i] for i in 1:20)] . The second part, the dictionary lookup, does not work and gives me an error so I must be doing something wrong.

Are dictionary lookups valid in an LP problem? Do I need to convert this to something else?

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
Eddie
  • 197
  • 4

1 Answers1

9

You can linearize the objective as follows.

Let binary decision variable $x_i$ indicate whether item $i$ is chosen, and let binary decision variable $y_c$ indicate whether the count of chosen items is $c$. Let $w_i$ be the weight of item $i$, and let $b_c$ be the bonus/penalty for choosing $c$ items. The problem is to maximize $$\sum_i w_i x_i + \sum_c b_c y_c$$ subject to \begin{align} \sum_i w_i x_i &\le W \tag1\\ \sum_c y_c &= 1 \tag2 \\ \sum_c c y_c &= \sum_i x_i \tag3 \end{align} Constraint $(1)$ is the usual knapsack constraint. Constraints $(2)$ and $(3)$ enforce $y_c=1 \iff \sum_i x_i = c$.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Hi @RobPratt, followup question for you if I may. How would this work if pairs of items had bonuses for being chosen together? Example, Item1 and Item2 has bonus of 4 if they are both in the knapsack. Each item will have a bonus with each other item. – Eddie Nov 17 '21 at 00:41
  • Add $4 x_1 x_2$ to the objective, which you can linearize by replacing $x_1 x_2$ with variable $z_{1,2}$ and imposing linear constraints $z_{1,2}\le x_1$ and $z_{1,2}\le x_2$. – RobPratt Nov 17 '21 at 01:36
  • If you have a penalty (rather than a bonus) for including both $i$ and $j$, you need to impose instead $z_{i,j} \ge x_i + x_j -1$ and $z_{i,j} \ge 0$. – RobPratt Nov 17 '21 at 02:06
  • @RobPratt, thanks for your interesting answer. Would you say please, what do the $c$ set elements mean? is there a simple group like ${c1,\dots,c5}$ to define five categories? or it is a nested set like a tuple? – A.Omidi Nov 17 '21 at 09:14
  • Here, $c\in{0,1,\dots,20}$ because it is the count of chosen items. – RobPratt Nov 17 '21 at 13:08
  • @RobPratt, many thanks DR. As the problem is interesting to me, I have tried to write that. I defined items as $i \in {i1, \dots, i20 }$ and $c$ based on what you suggested. Also, with $b_c =[0,-3,2,1.5,6,-4,-4,\dots, -4]$. The problem is solved without any issue, but what I am interested to know is how classification the items w.r.t the items $c$! As the second constraint just allowed to choose exactly one item in $c$, what does exactly the classification mean? – A.Omidi Nov 17 '21 at 15:15
  • The index $c$ represents not an item but instead the number of items chosen. For example, if three items $1,6,9$ are chosen, then $x_1=x_6=x_9=1$, all other $x_i=0$, $y_3=1$, and all other $y_c=0$. – RobPratt Nov 17 '21 at 17:02
  • @RobPratt, it now makes sense. Many thanks. – A.Omidi Nov 18 '21 at 04:32
  • @RobPratt thanks for the previous answer. Another followup, if I may. Let's say there are 10 groups each with up to 5 items. Each group has one special item and you must choose only one, let's call that group the "special group". There's a bonus of 4 if you take 1 more item from the special group, 8 bonus if you pick two. What I have tried is having g[1:10] which identifies the special group, then a[5row, 10col] which tells me how many items were taken from each group. I tried creating a new variable b[1:5] (max # of items) to try [i=1:5], b[i] <= sum(g[j] * a[i,j] for j in 1:10) – Eddie Nov 19 '21 at 02:00
  • My goal here was that since I only care about my special group, I would multiply each group's item count in a by whether it's the special group in g and storing that in b to calculate the bonus. This introduces a quadratic constraint which is not allowed in my solver. How would you go about this problem? I'm new to all this so sorry for the poor syntax. – Eddie Nov 19 '21 at 02:00
  • Please create a new question for this. – RobPratt Nov 19 '21 at 02:15
  • Apologies, just created the question, thank you again! link – Eddie Nov 19 '21 at 04:09