Advanced Search
Article Contents
Article Contents

An exact algorithm for 0-1 polynomial knapsack problems

Abstract Related Papers Cited by
  • In this paper we propose an exact method for the 0-1 polynomial knapsack problem. The algorithm seeks the exact optimal solution of the problem by a back-tracking branch-and-bound procedure. The upper bounds are computed by a Lagrangian dual search where the Lagrangian relaxations are solved by the maximum-flow method. Heuristic procedures are derived to search for feasible solutions and thus to improve the performance of the algorithm. Promising computational results are reported for test problems with both single constraint and multiple constraints.
    Mathematics Subject Classification: Primary: 90C09; 90C10; Secondary: 90C30.


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

Article Metrics

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

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint