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.

• 저널Management Science · 25(9) · 884–894
• 토픽Optimization and Mathematical Programming · Control and Systems Engineering
• DOI10.1287/mnsc.25.9.884
• 저자Ronald D. Armstrong, Wade D. Cook, Fernando Palacios-Gómez