Branch and Bound for Retail Discount Knapsack Problem
We have discussed dynamic programming extensively. Today we introduce branch and bound algorithm.
Take a simple zero-one knapsack problem with 3 items A, B, C. Essentially, it’s a binary tree for 3 items: for each item, either take it or not take it. In this case the tree depth is 3. By default, the complexity is exponential.
Branch is about figuring out which item to take at any node, while bound is about calculating potentials and pruning nodes if they can’t beat the current best deal. In worse case, it’s exponential, but it’s quite good in practice because of pruning (bound).
Branch
We usually take the next available item with best per unit value, with some small variations.
Bound
We have a variety of choices, for example,
- Assuming we branch by the static ordering of the items, we can calculate potential at a constant time as in dynamic programming.
- Linear programming relaxation, which calculates potentials by enumerating remaining items. (Search online to get more details.)
We can have even more aggressive potential calculation, however, more aggressive doesn’t mean more effective. If it helps pruning, great, but if not, it’s spinning CPU with potential calculation. In my experiment with retail discount, static bound works better overall than linear programming relaxation one.
Lastly, a short comparison with dynamic programming. In fact, they’re similar in both take-it-or-not-take-it part and pruning. The key difference is that dynamic programming employs cache, which turns exponential into pseudo-polynomial.
Related: Retail Discount Concurrency – Best Deal Knapsack Problem
Related: Dynamic Programming for Retail Discount Knapsack Problem