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.\nThis 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.\nFurthermore, this paper demonstrates that dynamic programming can be used to generate sensitivity analysis information for multiple choice knapsack problems.