Forest Harvesting and Minimum Cuts
Abstract
In this paper we discuss two forest harvesting optimization problems that
arise in forest management. We consider one-stage decision problems
in which the forest to be managed is partitioned into cells
and the decision is to be made as to which cells to harvest. There
are competing concerns to consider in assessing the value
of a particular harvesting decision: the first has to do with the value of
the timber harvested, and the second has to do with assessing the relative
values of the resulting spatial layout from a wildlife habitat point of view.
The two problems that we consider are similar, but assess the relative merits
of resulting spatial layouts somewhat differently and therefore have different
objective functions to be optimized.
The first problem we consider assigns benefits for
harvesting cells and penalties for harvesting adjacent cells;
the second problem considered assigns benefits for harvesting cells as well
as benefits for creating borders that separate harvested and unharvested cells.
We show that both forest harvesting problems can be interpreted as
instances of the Generalized Independent Set graph optimization problem, which
we introduce in this paper. Generalized Independent Set is a generalization of the
well-known Independent Set graph optimization problem (a set of nodes in a graph
is said to be independent if no two nodes in the set are adjacent).
When the underlying graph is bipartite, we derive an
efficient solution method for Generalized Independent Set via network flow methods.
If the cell structure is grid-like in the forest harvesting
problems, then an instance of either forestry problem can be reduced
to an instance of Generalized Independent Set on a bipartite graph. For such
instances we developed efficient algorithms for determining an optimal harvesting
strategy. The running time is O(n
logn), where n is the number of
cells in the land area to be spatially managed.
Download Information
Click on the following title to view and download the paper in PostScript format.
- Forest Harvesting and Minimum Cuts (26 pages, 196 KB)
,
- Dorit S. Hochbaum and Anu Pathria. Forest Science, 43:4, Nov 1997, 544-554.
dorit@hochbaum.ieor.berkeley.edu
7/29/98