Operations Research Transactions ›› 2013, Vol. 17 ›› Issue (1): 44-58.

• Original Articles • Previous Articles     Next Articles

Direct algorithm for continuous separable Knapsack problem

ZHU Tingting1, CHEN Wei1, CHEN Juanjuan1, SUN Wenhao1   

  1. 1. College of Science, Shanghai University
  • Online:2013-03-15 Published:2013-03-15

Abstract:  The quadratic Knapsack problem is NP-hard. In this paper, a direct algorithm is proposed for an ordinary continuous separable quadratic Knapsack problem with a single linear constraint and box constrains. According to the special structure model,  the optimal value of all the variables can be fixed gradually by adjusting the range of the Lagrangian multiplier for the linear constrain and by judging whether the variables of the first power in the objective function satisfy the box constraints. Finally the feasibility and efficiency of the algorithm are illustrated through the comparison of experimental results.

Key words: quadratic Knapsack problem, separable, Lagrangian multiplier, box constrains