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.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
3
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.
-
1$\begingroup$ In this formulation you pay "per violation" , and not "by violating" $\endgroup$– SuneAug 29, 2020 at 13:29
-
$\begingroup$ Not sure which interpretation was intended. $\endgroup$– RobPrattAug 29, 2020 at 14:39
-
$\begingroup$ Neither am I, so it's fine both are represented $\endgroup$– SuneAug 29, 2020 at 14:52
$\begingroup$
$\endgroup$
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.
