|
|||||
|
|
| SENSITIVITY ANALYSIS OF THE KNAPSACK PROBLEM： TIGHTER LOWER AND UPPER BOUND LIMITS | |
| 引用本文： | Tarik BELGACEM~1 Mhand HIFI~2 ~1CES-CNRS UMR 8174,Equipe CERMSEM,UniversitéParis 1 Panthon-Sorbonne 106-112,Boulevard de l''Hital,75647 Paris cedex 13,France MIS,Axis:Discrete Optimization and Re-optimization,Universitéde Picardie Jules Verne 33 rue Saint Leu,80039 Amiens cedex 01,France. SENSITIVITY ANALYSIS OF THE KNAPSACK PROBLEM： TIGHTER LOWER AND UPPER BOUND LIMITS[J]. 系统科学与系统工程学报(英文版), 2008, 17(2): 156-170. DOI: 10.1007/s11518-008-5073-y |
| 作者姓名： | Tarik BELGACEM~1 Mhand HIFI~2 ~1CES-CNRS UMR 8174 Equipe CERMSEM UniversitéParis 1 Panthon-Sorbonne 106-112 Boulevard de l''Hital 75647 Paris cedex 13 France MIS Axis:Discrete Optimization and Re-optimization Universitéde Picardie Jules Verne 33 rue Saint Leu 80039 Amiens cedex 01 France |
| 作者单位： | Tarik BELGACEM（CES-CNRS UMR 8174, Equipe CERMSEM, Universite Paris I Panthon-Sorbonne 106-112, Boulevard de l'Hopital, 75647 Paris cedex 13, France） ;Mhand HIFI（MIS, Axis: Discrete Optimization and Re-optimization, Universite de Picardie Jules Verne33 rue Saint Leu, 80039 Amiens cedex 01, France mhand.） ; |
| 基金项目： | The original version was presented on ICSSM'06. |
| 摘 要： | 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. |
| 关 键 词： | 组合最优化系统 背包问题 灵敏度分析 规划论 |
Sensitivity analysis of the knapsack problem: Tighter lower and upper bound limits |
|
| Tarik Belgacem,Mhand Hifi. Sensitivity analysis of the knapsack problem: Tighter lower and upper bound limits[J]. Journal of Systems Science and Systems Engineering, 2008, 17(2): 156-170. DOI: 10.1007/s11518-008-5073-y | |
| Authors: | Tarik Belgacem Mhand Hifi |
| Affiliation: | 1. CES-CNRS UMR 8174, Equipe CERMSEM, Universite Paris I Panthon-Sorbonne 106-112, Boulevard de l'Hopital, 75647 Paris cedex 13, France 2. MIS, Axis: Discrete Optimization and Re-optimization, Universite de Picardie Jules Verne33 rue Saint Leu, 80039 Amiens cedex 01, France mhand. |
| 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. |
| Keywords: | Combinatorial optimization knapsack sensitivity analysis |
| 本文献已被 维普 万方数据 SpringerLink 等数据库收录！ | |