An algorithm for large-scale nonliner knapsack : problems and extensions

Abstract

In this dissertation, an algorithm was developed to solve large scale discrete nonlinear knapsack problems (NKP) with multiple resource constraints. The algorithm is essentially a dynamic programming technique in a sense that the problem is decomposed into smaller subproblems. The concept of imbedded state space is incorporated in the algorithm to convert the multi-dimensional state variable problem to a single-dimensional state variable problem. The combinatorial nature of NKP and the dimensionality of state variables will result in the enumeration of an increasingly large vector of possible solutions at each stage. Several efforts were made to reduce the size of this vector. The principle three efforts are: (1) the elimination of those state-space solutions leading to an infeasible solution, (2) the elimination of those solution points which consume more of the resources and provide a smaller amount of return, (3) the elimination of the state-space solutions which will result (in preceding stages) in a return less than the predetermined lower bound. The initial lower and upper bounds are determined using the solution to a surrogate problem. These bounds are then iteratively updated. The updated lower bound will result in the elimination of unnecessary computations, and the updated upper bound serves as a termination criterion to stop the computational process (at any stage) whenever the solution reaches this bound. As a useful application, the problem of finding the best set of strategies for the Texas highway maintenance and rehabilitation system was solved by the algorithm. First, a diverging branch dynamic programming model was developed for the problem. Each branch of the dynamic programming model is considered as a maintenance district, in which a set of maintenance strategies must be selected. The objective is to maximize the summation of calculated utilities subject to the limitation of three types of materials, two types of equipment, and two types of manpower. The results obtained by solving each branch (district) are then used for allocation of the state-wide highway maintenance budget through maintenance districts. That is, all the branches of the non-serial dynamic programming model are related to a single state variable (amount of the budget), while each branch of a serial dynamic programming problem with multi-dimensional state variables must be solved...