1

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.

Peter
  • 13

1 Answers1

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

Erwin Kalvelagen
  • 4,267
  • If $b_i$ are the variables, shouldn't it be $B=\sum_i b_i W_i$ where $W_i$ are the weights ? So that $B$ equals the total balance of the selected items. Or perhaps I misunderstood the interpretation of the $b_i$ variables. – Kuifje Mar 27 '18 at 07:45
  • 1
    I just meant: $b_i$ is the "balance" of item $i$ (assumed to be variable). If you want you can interpret $b_i=w_i x_i$. – Erwin Kalvelagen Mar 27 '18 at 07:51
  • @ErwinKalvelagen: brilliant! Very elegant solution, thank you – Peter Mar 29 '18 at 12:17