5
$\begingroup$

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?

$\endgroup$

1 Answer 1

9
$\begingroup$

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$.

$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$
    – Eddie
    Commented Nov 17, 2021 at 0:41
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Commented Nov 17, 2021 at 1:36
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Commented Nov 17, 2021 at 2:06
  • $\begingroup$ @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? $\endgroup$
    – A.Omidi
    Commented Nov 17, 2021 at 9:14
  • $\begingroup$ Here, $c\in\{0,1,\dots,20\}$ because it is the count of chosen items. $\endgroup$
    – RobPratt
    Commented Nov 17, 2021 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.