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

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 of the optimum of a max-min combinatorial optimization problem, namely the Knapsack Sharing Problem (KSP), to the perturbation of the profit of an arbitrary item. We mainly establish the interval limits of each perturbed item by applying a reduction of the original problem into a series of single knapsack problems. We propose a solution procedure in order to establish these interval limits. The principle of the method is to stabilize the optimal solution in the perturbed problem, following two cases: (i) when the item belongs to an optimal class, and (ii) when the item belongs to a non optimal class. We also consider either the problem admits a unique or multiple optimal classes. Finally, we evaluate the effectiveness of the proposed solution procedure on several problem instances of the literature

Keywords: Sensitivity analysis; knapsack sharing; max-min; combinatorial optimization; optimality (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 International Transactions in Operational Research, 15, (1), 2008, pp.35-49

Downloads: (external link)
https://shs.hal.science/halshs-00188334 (application/pdf)
https://doi.org/10.1111/j.1475-3995.2007.00619.x
Our link check indicates that this URL is bad, the error code is: 403 Forbidden (https://doi.org/10.1111/j.1475-3995.2007.00619.x [302 Found]--> https://onlinelibrary.wiley.com/doi/10.1111/j.1475-3995.2007.00619.x)

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:b07064

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 ().