A branch and search algorithm for a class of nonlinear knapsack problems

Kamlesh Mathur; Harvey M. Salkin; Susumu Morito

doi:10.1016/0167-6377(83)90047-0

A branch and search algorithm for a class of nonlinear knapsack problems

Kamlesh Mathur^*, Harvey M. Salkin, Susumu Morito

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

42 Citations (Scopus)

Abstract

This paper discusses a class of nonlinear knapsack problems where the objective function is quadratic. The method is a branch and search procedure which includes an efficient algorithm to find the continuous (relaxed) solution and a reduction rule which computes tight lower and upper bounds on the integer variables.

Original language	English
Pages (from-to)	155-160
Number of pages	6
Journal	Operations Research Letters
Volume	2
Issue number	4
DOIs	https://doi.org/10.1016/0167-6377(83)90047-0
Publication status	Published - 1983
Externally published	Yes

Keywords

capital budgeting
integer programming
Nonlinear knapsack problem

ASJC Scopus subject areas

Management Science and Operations Research
Statistics, Probability and Uncertainty
Discrete Mathematics and Combinatorics
Modelling and Simulation

Access to Document

10.1016/0167-6377(83)90047-0

Cite this

@article{55b9eda4a8a04577ac51722c86b7085d,

title = "A branch and search algorithm for a class of nonlinear knapsack problems",

abstract = "This paper discusses a class of nonlinear knapsack problems where the objective function is quadratic. The method is a branch and search procedure which includes an efficient algorithm to find the continuous (relaxed) solution and a reduction rule which computes tight lower and upper bounds on the integer variables.",

keywords = "capital budgeting, integer programming, Nonlinear knapsack problem",

author = "Kamlesh Mathur and Salkin, {Harvey M.} and Susumu Morito",

year = "1983",

doi = "10.1016/0167-6377(83)90047-0",

language = "English",

volume = "2",

pages = "155--160",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - A branch and search algorithm for a class of nonlinear knapsack problems

AU - Mathur, Kamlesh

AU - Salkin, Harvey M.

AU - Morito, Susumu

PY - 1983

Y1 - 1983

N2 - This paper discusses a class of nonlinear knapsack problems where the objective function is quadratic. The method is a branch and search procedure which includes an efficient algorithm to find the continuous (relaxed) solution and a reduction rule which computes tight lower and upper bounds on the integer variables.

AB - This paper discusses a class of nonlinear knapsack problems where the objective function is quadratic. The method is a branch and search procedure which includes an efficient algorithm to find the continuous (relaxed) solution and a reduction rule which computes tight lower and upper bounds on the integer variables.

KW - capital budgeting

KW - integer programming

KW - Nonlinear knapsack problem

UR - http://www.scopus.com/inward/record.url?scp=0020843380&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020843380&partnerID=8YFLogxK

U2 - 10.1016/0167-6377(83)90047-0

DO - 10.1016/0167-6377(83)90047-0

M3 - Article

AN - SCOPUS:0020843380

SN - 0167-6377

VL - 2

SP - 155

EP - 160

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

A branch and search algorithm for a class of nonlinear knapsack problems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this