An Algorithm for a Nonlinear Discontinuous Knapsack Problem

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.