Sensitivity analysis of the knapsack sharing problem: perturbation of the weight

Tarik Belgacem and Mhand Hifi
Additional contact information
Tarik Belgacem: Centre d'Economie de la Sorbonne
Mhand Hifi: LaRIA et Centre d'Economie de la Sorbonne

Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne

Abstract: In this paper, we study the sensitivity analysis of the optimum of the knapsack sharing problem (KSP) to the perturbation of the weight of an arbitrary item. We determine the interval limits of the weight of each perturbed item using a heuristic approach which reduces the original problem to a series of single knapsackk problems. A perturbed item belongs either to an optimal class, or to a non-optimal class. We evaluate the performance of the proposed heuristic on a set problem instances of the literature. Encouraging results are obtained

Keywords: Stability; knapsack sharing problem; combinatorial optimization; knapsack problem (search for similar items in EconPapers)
JEL-codes: C44 C61 C63 (search for similar items in EconPapers)
Pages: 17 pages
Date: 2007-11
References: Add references at CitEc
Citations:

Published in Computers & operations research, 35, (1), 2008, pp.295-308

Downloads: (external link)
https://shs.hal.science/halshs-00188333 (application/pdf)
https://doi.org/10.1016/j.cor.2006.02.025

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:mse:cesdoc:b07063

Access Statistics for this paper

More papers in Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().