On the supermodular knapsack problem

On the supermodular knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor19891002
Country: Netherlands
Volume: 45
Issue: 2
Start Page Number: 295
End Page Number: 309
Publication Date: Oct 1989
Journal: Mathematical Programming
Authors: ,
Keywords: knapsack problem
Abstract:

In this paper the authors introduce binary knapsack problems where the objective function is nonlinear, and investigate their Lagrangean and continuous relaxations. Some of our results generalize previously known theorems concerning linear and quadratic knapsack problems. They investigate in particular the case in which the objective function is supermodular. Under this hypothesis, although the problem remains NP-hard, the authors show that its Lagrangean dual and its continuous relaxation can be solved in polynomial time. They also comment on the complexity of recognizing supermodular functions. The particular case in which the knapsack constraint is of the cardinality type is also addressed and some properties of its optimal value as a function of the right hand side are derived.

Reviews

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