Solving the generalized knapsack problem with variable coefficients

In this article the authors present methods based on Lagrangian duality and decomposition techniques for the generalized knapsack problem with variable coefficients. The Lagrangian dual is solved with subgradient optimization or interval bisection. They also describe a heuristic that yields primal feasible solutions. Combining the Lagrangian relaxation with a primal (Benders) subproblem yields the subproblem phase in cross decomposition. By using averages in this procedure, the authors get the new mean-value cross-decomposition method. Finally, they describe how to insert this into a globally convergent genealized Benders decomposition framework, in the case that there is a duality gap. Encouraging computational results for the optimal generating unit commitment problem are presented.