concentration constraint for knapsack problem

Question

I do have a question related to a 0-1 knapsack problem:

I formulated a model with quite a lot of constraints and an objective function on maximizing “balance”. I solved the problem using one of the available commercial solvers (lindo systems). However, would like to put in a couple of extra constraints like;

“the item with the highest balance cannot account for more than 1% of the total balance” (of the solution)

“the item with the 2nd highest balance cannot account for more than 0.5% of the total balance”

Can anyone help me with a solution for such a problem? I have an engineering background, but my math skills are a rusty, so pointers in the right direction would be helpful already.

Answer 1

I formulated a model with quite a lot of constraints

A knapsack problem has one constraint. If you have many constraints, I would not call it a knapsack problem.

“the item with the highest balance cannot account for more than 1% of the total balance”

\begin{align} & B = \sum_i b_i\\ & 0 \le b_i \le 0.01 \cdot B \end{align}

where $b_i$ is a variable indicating the balance of item $i$.

“the item with the 2nd highest balance cannot account for more than 0.5% of the total balance”

This is not so trivial. Here is one way with additional binary variables:

\begin{align} & b_i \le 0.005 \cdot B + \delta_i \cdot U\\ & \sum_i \delta_i = 1\\ & b_i \in [0,U]\\ & \delta_i \in \{0,1\} \end{align}

i.e. with one exception all $b_i$ should be less than 0.5% of $B$.