Title: Improved time and space complexity for Kianfar's inequality rotation algorithm

Authors: D. El Baz, M. Elkihel, L. Gely, G. Plateau

Addresses: LAAS-CNRS, Universite de Toulouse, 7, avenue du Colonel Roche, 31077 Toulouse Cedex 4, France. ' LAAS-CNRS, Universite de Toulouse, 7, avenue du Colonel Roche, 31077 Toulouse Cedex 4, France. ' LAAS-CNRS, Universite de Toulouse, 7, avenue du Colonel Roche, 31077 Toulouse Cedex 4, France. ' LIPN, UMR 7030 CNRS, Institut Galilee, Universite Paris 13, 99, avenue J.B. Clement, 93430 Villetaneuse, France

Abstract: In this paper, constraint rotation techniques are considered for preconditioning 0–1 knapsack problems. These techniques permit one to generate new inequalities by means of rotation of the original ones in order to approach the convex hull associated with the feasible integer points. The time and space complexities of Kianfar|s inequality rotation algorithm for combinatorial problems are improved. A revisited algorithm with order of (nC) and order of (C) representing, time and space complexity, respectively, is proposed, where C is smaller than the knapsack capacity. [Submitted 12 April 2008; Accepted 26 May 2008]

Keywords: knapsack problems; constraint rotation techniques; lifting; dynamic programming; Kianfar; inequality rotation; convex hull.

DOI: 10.1504/EJIE.2009.021593

European Journal of Industrial Engineering, 2009 Vol.3 No.1, pp.90 - 98

Published online: 30 Nov 2008 *

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