such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. Previous exact methods for solving this problem make use of mixed-integer linear programming solvers. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments by 4.5 times on average for all instances reported in the literature. Our algorithm is simple: a basic implementation takes less than 200 lines of code. More drastic performance improvements are seen for more challenging instances: on 20% of instances, our algorithm is at least 64 times faster, and we solved 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. This dynamic program relaxes the problem from bilevel to \(2n\)-level by ordering the items and solving an online version of the problem. The relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems.
A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints
\(\)
We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and \(n\) items. The objective is to select some items to pack into the first knapsack
such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. Previous exact methods for solving this problem make use of mixed-integer linear programming solvers. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments by 4.5 times on average for all instances reported in the literature. Our algorithm is simple: a basic implementation takes less than 200 lines of code. More drastic performance improvements are seen for more challenging instances: on 20% of instances, our algorithm is at least 64 times faster, and we solved 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. This dynamic program relaxes the problem from bilevel to \(2n\)-level by ordering the items and solving an online version of the problem. The relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems.
such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. Previous exact methods for solving this problem make use of mixed-integer linear programming solvers. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments by 4.5 times on average for all instances reported in the literature. Our algorithm is simple: a basic implementation takes less than 200 lines of code. More drastic performance improvements are seen for more challenging instances: on 20% of instances, our algorithm is at least 64 times faster, and we solved 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. This dynamic program relaxes the problem from bilevel to \(2n\)-level by ordering the items and solving an online version of the problem. The relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems.