Abstract:

 Quadratic knapsack problem is NP hard. This paper presents an algorithm to directly obtain a local optimal solution of a separable quadratic knapsack problem. By analyzing the structural characteristics of the problem, we study the relations between Lagrangian λ and the optimal solution. An algorithm is presented in which the Lagrangian λ is adjusted to give a local optimal solution. Computational complexity is O(n). 

Key words: quadratic knapsack problem; KarushKuhnTucker (KKT) condition; separable; Lagrangian