Convergent Lagrangian and domain cut method for nonlinear knapsack problems

Convergent Lagrangian and domain cut method for nonlinear knapsack problems

0.00 Avg rating0 Votes
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: , , ,
Keywords: knapsack problem
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.