Article ID: | iaor200922520 |
Country: | United States |
Volume: | 42 |
Issue: | 1 |
Start Page Number: | 67 |
End Page Number: | 104 |
Publication Date: | Jan 2009 |
Journal: | Computational Optimization and Applications |
Authors: | Wang J, Li D, Sun X L, McKinnon K I M |
Keywords: | knapsack problem |
The nonlinear knapsack problem, which has been widely studied in the OR literature, is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to separable nondecreasing constraints. In this paper we develop a convergent Lagrangian and domain cut method for solving this kind of problems. The proposed method exploits the special structure of the problem by Lagrangian decomposition and dual search. The domain cut is used to eliminate the duality gap and thus to guarantee the finding of an optimal exact solution to the primal problem. The algorithm is first motivated and developed for singly constrained nonlinear knapsack problems and is then extended to multiply constrained nonlinear knapsack problems. Computational results are presented for a variety of medium– or large–size nonlinear knapsack problems. Comparison results with other existing methods are also reported.