Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.02.025 Byline: T. Belgacem (b), M. Hifi (a)(b) 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 knapsack 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 of problem instances of the literature. Encouraging results are obtained. Author Affiliation: (a) LaRIA, Universite de Picardie Jules Verne, 5 rue du Moulin Neuf, 80000 Amiens, France (b) CERMSEM, Universite de Paris 1, 106-112 boulevard de l'HA[acute accent]pital, 75647 Paris cedex 13, France

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2005.10.004 Byline: M. Hifi, M. Michrafy Abstract: In this paper, we optimally solve the disjunctively constrained knapsack problem (DCKP), which is a variant of the standard knapsack problem with special disjunctive constraints. First, we develop a generic exact approach which can be considered as a three-phase procedure. The first phase tries to estimate a starting lower bound. The second phase applies a reduction procedure, combined with the lower bound, in order to fix some decision variables to the optimum. The third phase uses an exact branch and bound algorithm that identifies the optimal values of the free decision variables. Second, we design a specialized exact algorithm based upon a dichotomous search combined with a reduction procedure. Third and last, we propose a modified dichotomous search version which is based upon constructing an equivalent model to the DCKP, adding some dominating constraints, and injecting the so-called covering cut. We evaluate the performance of all versions of the algorithm and compare the obtained results to those of other exact algorithms of the literature. Encouraging results have been obtained. Author Affiliation: LaRIA, Universite de Picardie Jules Verne, 5 rue du Moulin Neuf, 80000 Amiens, France