How to optimize on a fixed-cost based on number of results?

Question

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?

Answer 1

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