This issuePrevious ArticleAn empirical study on discrete optimization models for
portfolio selectionNext ArticleDeterministic modeling of whole-body sheep metabolism
A Lagrangian dual and surrogate method for multi-dimensional
quadratic knapsack problems
Quadratic 0-1 knapsack problems have a variety
of applications in various areas such as flexible manufacturing systems, location
of transportation facilities and telecommunications. In this paper we present a branch-and-bound method for solving
multi-dimensional quadratic 0-1 knapsack problems. Outer approximation and bundle method
are used to compute the Lagrangian bound where the
Lagrangian relaxation is solved by the maximum flow algorithm.
We also present a surrogate constraint heuristic for finding feasible solutions.
Preliminary computational results for small to medium size test problems are reported.