Filtering Bounded Knapsack Constraints in Expected Sublinear Time

Yuri Malitsky, Meinolf Sellmann, Radoslaw Szymanek

AAAI 2010 pp. 141-146

doi:10.1609/AAAI.V24I1.7560 /aaai/2010/malitsky2010aaai-filtering/

Abstract

We present a highly efficient incremental algorithm for propagating bounded knapsack constraints. Our algorithm is based on the sublinear filtering algorithm for binary knapsack constraints by Katriel et al. and achieves similar speed-ups of one to two orders of magnitude when compared with its linear-time counterpart. We also show that the representation of bounded knapsacks as binary knapsacks leads to ineffective filtering behavior. Experiments on standard knapsack benchmarks show that the new algorithm significantly outperforms existing methods for handling bounded knapsack constraints.

PDF AAAI Semantic Scholar

Cite

Text

Malitsky et al. "Filtering Bounded Knapsack Constraints in Expected Sublinear Time." AAAI Conference on Artificial Intelligence, 2010. doi:10.1609/AAAI.V24I1.7560

Markdown

[Malitsky et al. "Filtering Bounded Knapsack Constraints in Expected Sublinear Time." AAAI Conference on Artificial Intelligence, 2010.](https://mlanthology.org/aaai/2010/malitsky2010aaai-filtering/) doi:10.1609/AAAI.V24I1.7560

BibTeX

@inproceedings{malitsky2010aaai-filtering,
  title     = {{Filtering Bounded Knapsack Constraints in Expected Sublinear Time}},
  author    = {Malitsky, Yuri and Sellmann, Meinolf and Szymanek, Radoslaw},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2010},
  pages     = {141-146},
  doi       = {10.1609/AAAI.V24I1.7560},
  url       = {https://mlanthology.org/aaai/2010/malitsky2010aaai-filtering/}
}