An Algorithm for a Nonlinear Discontinuous Knapsack Problem
R. D. Armstrong, W. D. Cook, F. E. Palacios-Gomez
Management Science · 1979 · Volume 25 · Issue 9
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
Enable JavaScript for citation tools and additional paper interactions.