Back to Search
Start Over
Sensitivity Analysis of the Knapsack Problem: Tighter Lower and Upper Bound Limits
- Source :
- Journal of Systems Science and Systems Engineering, Journal of Systems Science and Systems Engineering, Springer Verlag (Germany), 2008, 17 (2), pp.156-170. ⟨10.1007/s11518-008-5073-y⟩
- Publication Year :
- 2008
- Publisher :
- HAL CCSD, 2008.
-
Abstract
- In this paper, we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items. We propose a polynomial heuristic in order to establish both lower and upper bound limits of the sensitivity interval. The aim is to stabilize any given optimal solution obtained by applying any exact algorithm. We then evaluate the effectiveness of the proposed solution procedure on an example and a set of randomly generated problem instances.
- Subjects :
- Mathematical optimization
021103 operations research
Combinatorial optimization
Continuous knapsack problem
0211 other engineering and technologies
Perturbation (astronomy)
0102 computer and information sciences
02 engineering and technology
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Upper and lower bounds
01 natural sciences
Exact algorithm
sensitivity analysis
knapsack
Knapsack problem
010201 computation theory & mathematics
Control and Systems Engineering
Mathematics
Information Systems
Subjects
Details
- Language :
- English
- ISSN :
- 10043756 and 18619576
- Database :
- OpenAIRE
- Journal :
- Journal of Systems Science and Systems Engineering, Journal of Systems Science and Systems Engineering, Springer Verlag (Germany), 2008, 17 (2), pp.156-170. ⟨10.1007/s11518-008-5073-y⟩
- Accession number :
- edsair.doi.dedup.....38708a28b38765854be2f7d3ce9a6a37
- Full Text :
- https://doi.org/10.1007/s11518-008-5073-y⟩