4
$\begingroup$

I wonder if there is an option in the knapsack problem which has a huge cost for 'out-of-capacity' instead of strictly limiting the constraint.

$\endgroup$
6
$\begingroup$

If "out of capacity" means "if you violate capacity, you get infinite capacity for a large cost" the problem reduces to solving a knapsack problem and checking if the profit of this is higher than all positive profits summed minus the large cost.

$\endgroup$
4
$\begingroup$

You can introduce a nonnegative surplus variable $y$ with large cost $M$ and maximize $\sum_j v_j x_j-M y$ subject to $\sum_j w_j x_j \le W+y$.

Alternatively, if you want to impose a one-time fixed cost $M$ if there is any violation, let $y$ be binary and change the constraint to $\sum_j w_j x_j \le W+Uy$, where $U$ is some upper bound.

$\endgroup$
3
  • 1
    $\begingroup$ In this formulation you pay "per violation" , and not "by violating" $\endgroup$ – Sune Aug 29 '20 at 13:29
  • $\begingroup$ Not sure which interpretation was intended. $\endgroup$ – RobPratt Aug 29 '20 at 14:39
  • $\begingroup$ Neither am I, so it's fine both are represented $\endgroup$ – Sune Aug 29 '20 at 14:52
1
$\begingroup$

If the intent is a per unit penalty, rather than a fixed penalty for violation regardless of the size of the violation, you can switch to a generalized assignment problem with three destinations. The first destination is the original knapsack, with its original capacity. The second destination is an "overflow knapsack" with a sufficiently large capacity. The third destination is "do not take", again with large capacity. The objective coefficient of an assignment to the original knapsack is unchanged. The objective coefficient of assignment to the overflow knapsack is the original coefficient for that critter minus a penalty. The objective coefficient for assignment to the do not take" destination is zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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