Exact Counting and~Sampling of Optima for the Knapsack Problem
J. Bossek, A. Neumann, F. Neumann, in: Learning and Intelligent Optimization, Springer-Verlag, Berlin, Heidelberg, 2021, pp. 40–54.
Download
No fulltext has been uploaded.
Conference Paper
| Published
| English
Author
Bossek, JakobLibreCat 
;
Neumann, Aneta;
Neumann, Frank
;
Neumann, Aneta;
Neumann, FrankDepartment
Abstract
Computing sets of high quality solutions has gained increasing interest in recent years. In this paper, we investigate how to obtain sets of optimal solutions for the classical knapsack problem. We present an algorithm to count exactly the number of optima to a zero-one knapsack problem instance. In addition, we show how to efficiently sample uniformly at random from the set of all global optima. In our experimental study, we investigate how the number of optima develops for classical random benchmark instances dependent on their generator parameters. We find that the number of global optima can increase exponentially for practically relevant classes of instances with correlated weights and profits which poses a justification for the considered exact counting problem.
Publishing Year
Proceedings Title
Learning and Intelligent Optimization
Page
40–54
ISBN
LibreCat-ID
Cite this
Bossek J, Neumann A, Neumann F. Exact Counting and~Sampling of Optima for the Knapsack Problem. In: Learning and Intelligent Optimization. Springer-Verlag; 2021:40–54. doi:10.1007/978-3-030-92121-7_4
Bossek, J., Neumann, A., & Neumann, F. (2021). Exact Counting and~Sampling of Optima for the Knapsack Problem. Learning and Intelligent Optimization, 40–54. https://doi.org/10.1007/978-3-030-92121-7_4
@inproceedings{Bossek_Neumann_Neumann_2021, place={Berlin, Heidelberg}, title={Exact Counting and~Sampling of Optima for the Knapsack Problem}, DOI={10.1007/978-3-030-92121-7_4}, booktitle={Learning and Intelligent Optimization}, publisher={Springer-Verlag}, author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={40–54} }
Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Exact Counting And~Sampling of Optima for the Knapsack Problem.” In Learning and Intelligent Optimization, 40–54. Berlin, Heidelberg: Springer-Verlag, 2021. https://doi.org/10.1007/978-3-030-92121-7_4.
J. Bossek, A. Neumann, and F. Neumann, “Exact Counting and~Sampling of Optima for the Knapsack Problem,” in Learning and Intelligent Optimization, 2021, pp. 40–54, doi: 10.1007/978-3-030-92121-7_4.
Bossek, Jakob, et al. “Exact Counting And~Sampling of Optima for the Knapsack Problem.” Learning and Intelligent Optimization, Springer-Verlag, 2021, pp. 40–54, doi:10.1007/978-3-030-92121-7_4.
Google Scholar
ISBN Search