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

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?

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$$.
• 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$. Nov 17, 2021 at 1: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$. Nov 17, 2021 at 2: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? Nov 17, 2021 at 9:14
• Here, $c\in\{0,1,\dots,20\}$ because it is the count of chosen items. Nov 17, 2021 at 13:08