The nonlinear knapsack problem - algorithms and applications Academic Article

abstract

• We present a survey of algorithms and applications for the nonlinear knapsack problem (or, the nonlinear resource allocation problem). In its most general form, the nonlinear knapsack problem will be defined as a nonlinear optimization problem with just one constraint, bounds on the variables, and, in some cases, a set of specially structured constraints such as generalized upper bounds (GUBs). This problem is encountered either directly, or as a subproblem, in a variety of applications, including production planning, financial modeling, stratified sampling, and capacity planning in manufacturing, health care, and computer networks. By taking advantage of the special structure of the problem, efficient solution methods can be developed. Problem classes addressed here include continuous and integer problems, convex and nonconvex problems, separable and nonseparable problems, and problems with additional specially structured constraints. 2002 Elsevier Science B.V. All rights reserved.

authors

• Shetty, Bala

published proceedings

• EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

altmetric score

• 3

author list (cited authors)

• Bretthauer, K. M., & Shetty, B.

citation count

• 174

complete list of authors

• Bretthauer, KM||Shetty, B

publication date

• May 2002

publisher

• Elsevier  Publisher

published in

• European Journal of Operational Research  Journal

keywords

• Integer Programming
• Nonlinear Knapsack Problems
• Nonlinear Programming
• Nonlinear Resource Allocation Problem

Digital Object Identifier (DOI)

• 10.1016/S0377-2217(01)00179-5

start page

• 459

end page

• 472

volume

• 138

issue

• 3

URL

• http://dx.doi.org/10.1016/s0377-2217(01)00179-5