Premium
Solving the generalized knapsack problem with variable coefficients
Author(s) -
Holmberg Kaj,
Jörnsten Kurt
Publication year - 1996
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199608)43:5<673::aid-nav5>3.0.co;2-2
Subject(s) - subgradient method , lagrangian relaxation , mathematics , knapsack problem , duality gap , mathematical optimization , strong duality , duality (order theory) , lagrange multiplier , heuristic , variable (mathematics) , decomposition , benders' decomposition , decomposition method (queueing theory) , optimization problem , discrete mathematics , mathematical analysis , ecology , biology
In this article we 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. We 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, we get the new mean‐value cross‐decomposition method. Finally, we describe how to insert this into a globally convergent generalized Benders decomposition framework, in the case that there is a duality gap. Encouraging computational results for the optimal generating unit commitment problem are presented. © 1996 John Wiley & Sons, Inc.