A review of the status and use of validation procedures for heuristics used in forest planning
Ключевые слова:
combinatorial optimization, extreme value theory, linear programming, mixed integer programming, operations researchАннотация
While there exist clear methods for validating and ensuring the quality of solutions generated by forest planning heuristic techniques, the use of these methods in the literature varies from one situation to the next. Based on our experience developing and using heuristic forest planning techniques, we describe six levels of heuristic validation that are currently in use, ranging from no validation (Level 1) on one end of the spectrum, to the comparison of heuristic technique solutions with an exact solution obtained using mathematical programming methods (Level 6) on the other end. The reasons why authors may choose or reviewers may require levels of validation are proposed. We do not believe that all research papers should be subjected to the highest level of validation, but suggest that authors of papers on forest planning techniques and reviewers associated with peer-reviewed journals try to place the level of validation within the larger scientific context, then determine an appropriate level of validation. Admittedly, this is problematic for review decisions, given the fact that reviewers may differ in opinion of what is appropriate. Four brief cases are provided to help one think through these issues. Ultimately, we hope that this discussion will lead to a reasoned approach for the use of validation processes in conjunction with the presentation of heuristic techniques, rather than the current ad-hoc process that, on one hand, relies on the valuable and careful thoughts of the reviewers, yet on the other hand, may be uneven in application. MCFNS-1:26-37.
Библиографические ссылки
Barr, R.S., B.L. Golden, J.P. Kelly, M.G.C. Resende, and W.R. Stewart, Jr. 1995. Designing and reporting on computational experiments with heuristic methods. Journal of Heuristics. 1(1): 9-32.
Barrett, T.M., and J.K. Gilless. 2000. Even-aged restrictions with sub-graph adjacency. Annals of Operations Research. 95(1-4): 159-175.
Barrett, T.M., J.K. Gilless, and L.S. Davis. 1998. Economic and fragmentation effects of clearcut restrictions. Forest Science. 44(4): 569-577.
Baskent, E.Z., and S. Keles. 2005. Spatial forest planning: A review. Ecological Modelling. 188(2-4): 145-173.
Berterretche, M., A.T. Hudak, W.B. Cohen, T.K. Maiersperger, S.T. Gower, and J. Dungan. 2005. Comparison of regression and geostatistical methods for mapping Leaf Area Index (LAI) with Landsat ETM+ data over a boreal forest. Remote Sensing of Environment. 96: 49-61.
Bertomeu, M., and C. Romero. 2001. Managing forest biodiversity: A zero-one goal programming approach. Agricultural Systems. 68(3): 197-213.
Bettinger, P., K. Boston, Y.-H. Kim, and J. Zhu. 2007. Landscape-level optimization using tabu search and stand density-related forest management prescriptions. European Journal of Operational Research. 176(2): 1265-1282.
Bettinger, P., and W. Chung. 2004. The key literature of, and trends in, forest-level management planning in North America, 1950-2001. The International Forestry Review. 6(1): 40-50.
Bettinger, P., D. Graetz, K. Boston, J. Sessions, and W. Chung. 2002. Eight heuristic planning techniques applied to three increasingly difficult wildlife planning problems. Silva Fennica. 36(2): 561-584.
Bettinger, P., D.L. Johnson, and K.N. Johnson. 2003. Spatial forest plan development with ecological and economic goals. Ecological Modelling. 169(2-3): 215-236.
Bettinger, P., and J. Sessions. 2003. Spatial forest planning: to adopt, or not to adopt? Journal of Forestry. 101(2):24-29.
Bettinger, P., J. Sessions, and K. Boston. 1997. Using Tabu search to schedule timber harvests subject to spatial wildlife goals for big game. Ecological Modelling. 94(2-3): 111-123.
Bettinger, P., J. Sessions, and K.N. Johnson. 1998. Ensuring the compatibility of aquatic habitat and commodity production goals in eastern Oregon with a Tabu search procedure. Forest Science. 44(1): 96-112.
Bettinger, P., and J. Zhu. 2006. A new heuristic for solving spatially constrained forest planning problems based on mitigation of infeasibilities radiating outward from a forced choice. Silva Fennica. 40(2): 315-333.
Borges, J.G., H.M. Hoganson, and D.W. Rose. 1999. Combining a decomposition strategy with dynamic programming to solve spatially constrained forest management scheduling problems. Forest Science. 45(2): 201-212.
Boston, K., and P. Bettinger. 1999. An analysis of Monte Carlo integer programming, simulated annealing, and tabu search heuristics for solving spatial harvest scheduling problems. Forest Science. 45(2): 292-301.
Boston, K. and P. Bettinger. 2001. Development of spatially feasible forest plans: A comparison of two modeling approaches. Silva Fennica. 35(4): 425-435.
Brumelle, S., D. Granot, M. Halme, and I. Vertinsky. 1998. A tabu search algorithm for finding good forest harvest schedules satisfying green-up constraints. European Journal of Operational Research 106(2-3): 408-424.
Carpenter, S.R. 2002. Ecological futures: Building an ecology of the long now. Ecology. 83: 2069-2083.
Cieszewski, C.J., M. Zasada, B.E. Borders, R.C. Lowe, J. Zawadzki, M.L. Clutter, and R.F. Daniels. 2004. Spatially explicit sustainability analysis of long-term fiber supply in Georgia, USA. Forest Ecology and Management. 187(2-3): 345-359.
Clark, M.M., R.D. Meller, and T.P. McDonald. 2000. A three-stage heuristic for harvest scheduling with access road network development. Forest Science. 46(2): 204-218.
Crowe, K., and J. Nelson. 2003. An indirect search algorithm for harvest-scheduling under adjacency constraints. Forest Science. 49(1): 1-11.
Dahlin, B., and O. Sallnas. 1993. Harvest scheduling under adjacency constraints - A case study from the Swedish subalpine region. Scandinavian Journal of Forest Research. 8: 281-290.
Dannenbring, D.G. 1977. Procedures for estimating optimal solution values for large combinatorial problems. Management Science. 23(12): 1273-1283.
Daust, D.K., and J.D. Nelson. 1993. Spatial reduction factors for strata-based harvest schedules. Forest Science. 39(1): 152-165.
Epstein, R., A. Weintraub, P. Sapunar, E. Nieto, J.B. Sessions, J. Sessions, F. Bustamante, and H. Musante. 2006. A combinatorial heuristic approach for solving real-sized machinery location and road design problems in forestry planning. Operations Research. 54(6): 1017-1027.
Falcão, A.O., and J.G. Borges. 2001. Designing an evolution program for solving integer forest management scheduling models: An application in Portugal. Forest Science. 47(2): 158-168.
Falcão, A.O., and J.G. Borges. 2002. Combining random and systematic search heuristic procedures for solving spatially constrained forest management scheduling models. Forest Science. 48(3): 608-621.
Garey, M.R., R.L. Graham, and D.S. Johnson. 1978. Performance guarantees for scheduling algorithms. Operations Research. 26(1): 3-21.
Golden, B.L., and F.B. Alt. 1979. Interval estimation of a global optimum for large combinatorial problems. Naval Research Logistics Quarterly. 26(1): 69-77.
Heinonen, T., and T. Pukkala. 2004. A comparison of one- and two-compartment neighbourhoods in heuristic search with spatial forest management goals. Silva Fennica. 38(3): 319-332.
Hertz, A., and M. Widmer. 2003. Guidelines for the use of meta-heuristics in combinatorial optimization. European Journal of Operational Research. 151(2): 247-252.
Hof, J.G., and L.A. Joyce. 1993. A mixed integer linear programming approach for spatially optimizing wildlife and timber in managed forest ecosystems. Forest Science. 39(4): 816-834.
Hof, J.G., and J.B. Pickens. 1991. Chance-constrained and choice-maximizing mathematical programs in renewable resource management. Forest Science. 37(1): 308-325.
Hoganson, H.M., and J.G. Borges. 1998. Using dynamic programming and overlapping subproblems to address adjacency in large harvest scheduling problems. Forest Science. 44(4): 526-538.
Hooker, J.N. 1995. Testing heuristics: We have it all wrong. Journal of Heuristics. 1(1): 33-42.
Howard, A.F., and J.S. Tanz. 1993. Establishing equitable contract rates for timber harvesting using deterministic simulation. Northern Journal of Applied Forestry. 10(1): 5-7.
Integrated Forest Management Laboratory. 2006. Forest management optimization site. University of New Brunswick, Fredericton, NB. http://ifmlab.for.unb.ca/fmos/ (accessed 7/26/07).
Jørgensen, R.M., H. Thomsen, and R.V.V. Vidal. 1992. The afforestation problem: A heuristic method based on simulated annealing. European Journal of Operational Research. 56(2): 184-191.
Koltz, S., N.L. Johnson, and C.B. Read. 1982. Encyclopedia of statistical sciences: Volume 2. John Wiley & Sons, New York.
Krcmar, E., B. Stennes, G.C. van Kooten, and I. Vertinsky. 2001. Carbon sequestration and land management under uncertainty. European Journal of Operational Research. 135(3): 616-629.
Kurttila, M., T. Pukkala, and J. Loikkanen. 2002. The performance of alternative spatial objective types in forest planning calculations: A case for flying squirrel and moose. Forest Ecology and Management. 166(1-3): 245-260.
Law, A.M., and W.D. Kelton. 1991. Simulation modeling and analysis. Second edition. McGraw-Hill, Inc. New York. 759 p.
Lee, S, and R.M. O'Keefe. 1994. Developing a strategy for expert system verification and validation. IEEE Transactions on Systems, Man, and Cybernetics. 24(4): 643-655.
Liu, G., S. Han, X. Zhao, J.D. Nelson, H. Wang, and W. Wang. 2006. Optimisation algorithms for spatially constrained forest planning. Ecological Modelling. 194(4): 421-428.
Lockwood, C., and T. Moore. 1993. Harvest scheduling with spatial constraints: a simulated annealing approach. Canadian Journal of Forest Research. 23(3): 468-478.
Los, M., and C. Lardinois. 1982. Combinatorial programming, statistical optimization and the optimal transportation network problem. Transportation Research - B. 16B(2): 89-124.
Lu, F., and L.O. Eriksson. 2000. Formation of harvest units with genetic algorithms. Forest Ecology and Management. 130(1-3): 57-67.
Martin, A., T. Achterberg, and T. Koch. 2006. MIPLIB 2003. Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB). Accessed 7/26/07 at http://miplib.zib.de/miplib2003.php
Martins, I., M. Constantino, and J.G. Borges. 2005. A column generation approach for solving a non-temporal forest harvest model with spatial structure constraints. European Journal of Operational Research. 161(2): 478-498.
Mastrolilli, M., and L. Bianchi. 2005. Core instances for testing: A case study. European Journal of Operational Research. 166(1): 51-62.
McDill, M.E., and J. Braze. 2001. Using branch and bound algorithm to solve forest planning problems with adjacency constraints. Forest Science. 47(3): 403-418.
McRoberts, K.L. 1971. A search model for evaluating combinatorially explosive problems. Operations Research. 19(6): 1331-1349.
Murray, A.T., and A. Weintraub. 2002. Scale and unit specification influences in harvest scheduling with maximum area restrictions. Forest Science. 48(4): 779-789.
Nalle, D.J., J.L. Arthur, and J. Sessions. 2002. Designing compact and contiguous reserve selection networks with a hybrid heuristic algorithm. Forest Science. 48(1): 59-68.
Nelson, J. and J.D. Brodie. 1990. Comparison of a random search algorithm and mixed integer programming for solving area-based forest plans. Canadian Journal of Forest Research. 20(7): 934-942.
O'Hara, A.J., B.H. Faaland, and B.B. Bare. 1989. Spatially constrained timber harvest scheduling. Canadian Journal of Forest Research. 19(6): 715-724.
Öhman, K., and T. Lamas 2005. Reducing forest fragmentation in long-term forest planning by using the shape index. Forest Ecology and Management. 212(1-3): 346-357.
Psaraftis, H.N. 1994. Review standards for OR/MS papers. OR/MS Today. 21(3): 54-57.
Pukkala, T., and M. Kurttila. 2005. Examining the performance of six heuristic optimisation techniques in different forest planning problems. Silva Fennica. 39(1): 67-80.
Rardin, R.L., and R. Uzsoy. 2001. Experimental evaluation of heuristic optimization algorithms: A tutorial. Journal of Heuristics. 7(3): 261-301.
Rosing, K.E., and C.S. ReVelle. 1997. Heuristic concentration: Two stage solution construction. European Journal of Operational Research. 97(1): 75-86.
Rosing, K.E., C.S. ReVelle, and J.C. Williams. 2002. Maximizing species representation under limited resources: A new and efficient heuristic. Environmental Modeling and Assessment. 7(2): 91-98.
Tarp, P., and F. Helles. 1997. Spatial optimization by simulated annealing and linear programming. Scandinavian Journal of Forest Research. 12(4): 390-402.
Tezuka, S. 1995. Uniform random numbers: Theory and practice. Kluwer Academic Publishers, Boston, MA. 228 p.
Van Deusen, P.C. 1999. Multiple solution harvest scheduling. Silva Fennica. 33(3): 207-216.
Weintraub, A., and A. Cholaky. 1991. A hierarchical approach to forest planning. Forest Science. 37(2): 439-460.
Weintraub, A., G. Jones, A. Magendzo, M. Meacham, and M. Kirby. 1994. A heuristic system to solve mixed integer forest planning models. Operations Research. 42(6): 1010-1024.
Weintraub, A., and J. Vera. 1991. A cutting plane approach for chance constrained linear programs. Operations Research. 39(5): 776-785.
Willers, J.L., T.L. Wagner, and R.A. Sequeira. 1995. Analysis of deterministic simulation models using methods applicable to two-way treatment structures without replication. Agronomy Journal. 87: 478-492.
Yoshimoto, A., J.D. Brodie, and J. Sessions. 1994. A new heuristic to solve spatially constrained long-term harvest scheduling problems. Forest Science. 40(3): 365-396.
Zanakis, S.H., and J.R. Evans. 1981. Heuristic optimization: Why, when, and how to use it. Interfaces. 11(5): 84-91.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Authors who publish with this journal agree to the following terms:- Authors grant the journal right of first publication, with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) following the publication by the journal, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
