Efficient Algorithm for Nonpoint Source Pollution Control Problems

Aziz Bouzaher, John B. Braden, Gary V. Johnson, Susan E. Murley
November 1991  [91-WP 78]

Download Full Text

Suggested citation:

Bouzaher, A., J. Braden, G. Johnson, and S. Murley. 1991. "Efficient Algorithm for Nonpoint Source Pollution Control Problems." Working paper 91-WP 78. Center for Agricultural and Rural Development, Iowa State University.


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.

Keywords: Dynamic programming, integer programming, microcomputers, environmental studies, agriculture.