Efficient Algorithm for Nonpoint Source Pollution Control Problems

A dynamic programming algorithm is proposed for a class of nonpoint source pollution control problems. The inherently combinatorial nature of these problems--stemming from the discrete nature of the decision variables, which are production and conservation practices--gives them a special knapsack structure with multiple right hand sides and additional multiple choice constraints. This paper focuses on the computer implementation of this algorithm and its numerical testing and behavior compared with standard integer programming codes. The results show the robustness and relative efficiency of the approach. Furthermore, this paper demonstrates that dynamic programming can be used to generate sensitivity analysis information for multiple choice knapsack problems.