Article: An adaptive algorithm for the knapsack problem: perturbation of the profit or weight of an arbitrary item Journal: European Journal of Industrial Engineering (EJIE) 2008 Vol.2 No.2 pp.134 - 152 Abstract: This paper solves the binary single-constrained Knapsack Problem (KP) and undertakes a sensitivity analysis of its optimum solution. Given a knapsack of capacity c, and a set of n items, with each item j, j = 1,…,n, characterised by a weight wj and a profit pj, the binary single-constrained KP picks a subset of these items with maximal total profit while obeying the constraint that the maximum total weight of the chosen items does not exceed c. This paper proposes an adaptive branch and bound tree search algorithm that exactly solves the problem, and provides the limits of the sensitivity intervals, which guarantee the stability of the optimal solution when the profit of any arbitrary item is perturbed. Next, the paper adapts the exact algorithm for the perturbation of the weight coefficient of an arbitrary item. The computational results demonstrate the effectiveness of the adaptive algorithm. [Received: 16 March 2007; Revised: 08 August 2007; Accepted: 16 November 2007] Inderscience Publishers - linking academia, business and industry through research

Title: An adaptive algorithm for the knapsack problem: perturbation of the profit or weight of an arbitrary item

Authors: Mhand Hifi, Hedi Mhalla, Slim Sadfi

Addresses: Laboratoire MIS, Axe Discrete Optimization and Reoptimization, Universite de Picardie Jules Verne, 33 rue du Saint-Leu, 80039 Amiens, France; CES, Equipe CERMSEM, Maison des Sciences Economiques, Universite de Paris 1 Pantheon-Sorbonne, 106–112 bd de l'Hopital 75013 Paris, France. ' Labortoire Finance Quantitative, IHEC, Sousse, Route Hzamia Sahloul 3, BP n 40 – 4054 Sousse, Tunisie. ' Laboratoire MIS, Axe Discrete Optimization and Reoptimization, Universite de Picardie Jules Verne, 33 rue du Saint-Leu, 80039 Amiens, France

Abstract: This paper solves the binary single-constrained Knapsack Problem (KP) and undertakes a sensitivity analysis of its optimum solution. Given a knapsack of capacity c, and a set of n items, with each item j, j = 1,…,n, characterised by a weight wj and a profit pj, the binary single-constrained KP picks a subset of these items with maximal total profit while obeying the constraint that the maximum total weight of the chosen items does not exceed c. This paper proposes an adaptive branch and bound tree search algorithm that exactly solves the problem, and provides the limits of the sensitivity intervals, which guarantee the stability of the optimal solution when the profit of any arbitrary item is perturbed. Next, the paper adapts the exact algorithm for the perturbation of the weight coefficient of an arbitrary item. The computational results demonstrate the effectiveness of the adaptive algorithm. [Received: 16 March 2007; Revised: 08 August 2007; Accepted: 16 November 2007]

Keywords: adaptive algorithm; combinatorial optimisation; knapsack problem; optimality; sensitivity analysis; profit; weight; arbitrary items.

DOI: 10.1504/EJIE.2008.017348

European Journal of Industrial Engineering, 2008 Vol.2 No.2, pp.134 - 152

Published online: 01 Mar 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: An adaptive algorithm for the knapsack problem: perturbation of the profit or weight of an arbitrary item

Keep up-to-date