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

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]