Several approaches exist to model the production, transport and delivery of sediment in watersheds but none of these include spatial optimality requirements. However, policy and decision makers dealing with environmental conservation and
land use planning often require identifying suitable sites for contributing to minimize sediment flow reaching riverbeds. This is the case for reforestation initiatives, which can have sediment flow minimization among their objectives. A Heuristic solution method has been previously developed for selecting a predefined number of cells in raster maps. Those cells are intended to be reforested in order to minimize sediment load at a given watershed outlet. These methods make use of a Single Flow Direction (SFD) raster map covering the watershed in order to construct a tree structure so that the outlet cell corresponds to the root node in the tree. Under the tree structure the sediment flow produced and accumulated in every cell follows a unique path until the root is reached. As a result the actual amount of sediment contributed by each node to the root can be determined. This paper proposes to extend an heuristic method in order to restrict the selection of the locations according to a budget constraint instead of a predefined number of cells. Thus the sediment minimization is reduced to a knapsack problem. The results of several experiments for searching optimal cells minimizing sediment reaching the outlet of two watersheds pertaining to South Dakota in the USA are reported. To measure the performance of the heuristic its results are compared with the ones obtained with an Integer Programming (IP) formulation. The comparison allows to conclude that the heuristic approach is suitable for selecting cells minimizing sediment flow under a budget constraint.