Advanced Search
Article Contents
Article Contents

A Lagrangian dual and surrogate method for multi-dimensional quadratic knapsack problems

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C10, 90C20; Secondary: 90C11.


    \begin{equation} \\ \end{equation}
  • 加载中

Article Metrics

HTML views() PDF downloads(95) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint