The Performance of the Modified Subgradient Algorithm on Solving the 0–1 Quadratic Knapsack Problem

Article type: Research Article

Authors: Sipahioglu, Aydin | Saraç, Tugba

Affiliations: Industrial Engineering Department of Eskisehir Osmangazi University, Meselik 26480, Eskisehir, Turkey, e-mail: asipahi@ogu.edu.tr; tsarac@ogu.edu.tr

Abstract: In this study, the performance of the modified subgradient algorithm (MSG) to solve the 0–1 quadratic knapsack problem (QKP) was examined. The MSG was proposed by Gasimov for solving dual problems constructed with respect to sharp Augmented Lagrangian function. The MSG has some important proven properties. For example, it is convergent, and it guarantees zero duality gap for the problems such that its objective and constraint functions are all Lipschtz. Additionally, the MSG has been successfully used for solving non-convex continuous and some combinatorial problems with equality constraints since it was first proposed. In this study, the MSG was used to solve the QKP which has an inequality constraint. The first step in solving the problem was converting zero-one nonlinear QKP problem into continuous nonlinear problem by adding only one constraint and not adding any new variables. Second, in order to solve the continuous QKP, dual problem with "zero duality gap" was constructed by using the sharp Augmented Lagrangian function. Finally, the MSG was used to solve the dual problem, by considering the equality constraint in the computation of the norm. To compare the performance of the MSG with some other methods, some test instances from the relevant literature were solved both by using the MSG and by using three different MINLP solvers of GAMS software. The results obtained were presented and discussed.

Keywords: quadratic knapsack problem, sharp augmented lagrangian function, MSG, integer programming

Journal: Informatica, vol. 20, no. 2, pp. 293-304, 2009