An Algorithm for a Nonlinear Discontinuous Knapsack Problem

R. D. Armstrong, W. D. Cook and F. E. Palacios-Gomez
Additional contact information
R. D. Armstrong: University of Texas, Austin
W. D. Cook: York University
F. E. Palacios-Gomez: University of Texas, Austin

Management Science, 1979, vol. 25, issue 9, 884-894

Abstract: This paper presents a solution procedure for a class of discontinuous nonlinear knapsack problems. These problems have a single linear constraint and a restriction that each variable must be either zero or take on a value within a specified interval. The objective function is separable and each term is concave within the interval. Problems of this type arise in capital budgeting and a particular application in the scheduling of pavement maintenance is given. The branch-and-bound algorithm developed to solve the problem considers an approximation-relaxation at each step. Computational experience with the algorithm and a brief overview of applications of the model are given.

Keywords: branch-and-bound; nonlinear programming algorithms; knapsack problem (search for similar items in EconPapers)
Date: 1979
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.25.9.884 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:25:y:1979:i:9:p:884-894

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().