Using the branch and bound algorithm to solve forest planning problems with adjacency constraints

This article describes an assessment of the branch and bound algorithm (BBA) for solving forest management planning problems with adjacency constraints. Four questions are addressed: (1) What are the current limits of off-the-shelf optimization software implementing the BBA in terms of types and sizes of problems that can be solved within a reasonable time? (2) To what degree can larger problems be solved if the solution tolerance gap is increased from the default 0.01%? (3) How much can solution times be reduced by increasing the tolerance gap? and (4) If the algorithm is stopped at a larger tolerance gap, how large is the true gap likely to be? To address these questions, 2,676 hypothetical, spatially explicit forest management problems with three planning periods and between 50 and 2,500 management units were created and then solved with CPLEX® Version 6.5 to tolerance gaps of 0.01%, 0.1%, 1%, or 2%. For forests with immature or regulated age–class distributions, the predicted average solution time to a tolerance gap of 0.01% was 7.6 and 17.4 min, respectively, for problems with 2,500 management units – the largest problems solved in this study. For overmature and old-growth forest problems, predicted average solution times to a 0.01% tolerance gap reached 4 hr at about 640 and 213 management units, respectively. Increasing the tolerance gap to 1% increased these limits to 1,420 and 235 units, respectively. Increasing the tolerance gap to 1% reduced solution times by at least 90% in 49% of the overmature forest cases and in 53% of the old-growth forest cases. In overmature and old-growth forest problems, the true gap averaged 0.28% and 0.41%, respectively, when the reported gap was 1%.