Introduction
In the field of constraint programming (CP), the knapsack constraint is a fundamental component used to model various optimization problems, including scheduling and resource allocation. The process of "filtering" these constraints involves pruning the search space by determining which items are mandatory or forbidden based on current profit and capacity bounds. While efficient sublinear-time algorithms have been developed for the Binary Knapsack Problem (2KP), the Bounded Knapsack Problem (BKP)—where items can have multiple copies—has traditionally relied on binary decomposition. This paper presents a novel, native filtering algorithm for BKP that achieves expected sublinear time, significantly outperforming standard decomposition methods.
The Bounded Knapsack Problem and the Symmetry Trap
The standard approach to handling BKP in CP solvers is to decompose each bounded item into a set of binary variables. However, this method is computationally expensive and mathematically "weak." Because multiple copies of the same item are identical, decomposition introduces significant symmetry into the search space. A solver might realize one copy is mandatory but fail to immediately infer the same for others, leading to redundant search effort. By treating bounded items natively, our algorithm avoids this "symmetry trap," allowing for more effective pruning and a drastically reduced search tree.
Sublinear Filtering with Finger Trees
To achieve high efficiency, we generalize the "strong skipping" technique. The core of our approach involves:
- Linear Relaxation: Items are sorted by efficiency (profit-to-weight ratio) to identify a critical item that defines the greedy solution.
- Finger Trees: We utilize finger trees—a specialized balanced search tree—to store item properties. This data structure enables the algorithm to "jump" over blocks of items that are guaranteed not to be mandatory, reducing the expected search time from $O(n)$ to approximately $O(\sqrt{n} \log n)$.
- Efficient Updates: Since item bounds change frequently during search, we implement a level-by-level update mechanism for the finger trees. This ensures that data structures are synchronized with minimal overhead, even when multiple bounds change simultaneously.
Experimental Evaluation
The algorithm was tested against standard knapsack benchmarks, including Uncorrelated (UC), Weakly Correlated (WC), Strongly Correlated (SC), and Almost Strongly Correlated (AS) distributions. We compared our native BKP filtering (bkp) against the traditional binary decomposition (bin).
Results and Discussion
Our experimental results demonstrate substantial improvements in both execution speed and search efficiency. The bkp algorithm is up to 80 times faster than the previous state-of-the-art linear-time approach. More importantly, the native handling of bounded items leads to a massive reduction in the search space. As shown in the node comparison figure above, the bkp method visited 99.5% fewer nodes than the binary representation in many instances.
As seen in the execution time comparison, the performance gap widens as the number of items or copies per item increases. In large-scale tests, the bkp method was over 750 times faster in total execution time compared to binary decomposition. While the worst-case performance remains linear, the expected sublinear behavior holds across a wide range of practical benchmarks.
Conclusion
By providing a native, sublinear-time filtering algorithm for bounded knapsack constraints, this work addresses a significant bottleneck in constraint-based optimization. The use of finger trees to enable strong skipping, combined with an efficient update strategy, allows for speedups of one to two orders of magnitude. This approach not only accelerates the filtering process itself but also fundamentally improves search efficiency by eliminating the symmetries inherent in binary decomposition.
Summary updated