\`x^2+y_1+z_12^34\`
Advanced Search
Advanced Search
Advanced Search
This issue Previous Article Next Article
Article Contents
Article Contents
2009, Volume 5, Issue 1: 47-60. Doi: 10.3934/jimo.2009.5.47
This issue Previous Article An empirical study on discrete optimization models for portfolio selection Next Article Deterministic modeling of whole-body sheep metabolism

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

  • 1.

    School of Management, Fudan University, Shanghai 200433

  • 2.

    Department of Mathematics, Shanghai University, Shanghai 200444

Received:  March 31, 2008
Revised:  September 30, 2008
Published:  December 2008
Abstract Related Papers Cited by
    Abstract
  • 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.

    Citation:
    shu

    \begin{equation} \\ \end{equation}
    • Related Papers
  • Cited by
  • Access History
  • 加载中
PDF
XML
Export Citation
SHARE
Email to a Friend

Article Metrics

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

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return
    Site map Copyright © 2023 American Institute of Mathematical Sciences