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

摘要

In tins study, the performance of the modilied subgradienl 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 lirst 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 compulation 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 MINI.P solvers of GAMS software. The results obtained were presented and discussed.