An exact algorithm for 0-1 polynomial knapsack problems

Xiaoling Sun; Hongbo Sheng; Duan Li

doi:10.3934/jimo.2007.3.223

Article Contents

2007, Volume 3, Issue 2: 223-232. Doi: 10.3934/jimo.2007.3.223

This issue Previous Article A smoothing scheme for optimization problems with Max-Min constraints Next Article Existence of closed graph, maximal, cyclic pseudo-monotone relations and revealed preference theory

An exact algorithm for 0-1 polynomial knapsack problems

1.
Department of Management Science, School of Management, Fudan University, Shanghai 200433, P. R.
2.
Department of Elementary Education, Tongling University, Tongling, Anhui 244000, P. R.
3.
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N. T., Hong Kong

Received: July 31, 2006

Revised: December 31, 2006

Published: March 2007

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C09; 90C10; Secondary: 90C30.

Citation:

Article Metrics

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

An exact algorithm for 0-1 polynomial knapsack problems

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

An exact algorithm for 0-1 polynomial knapsack problems

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content