Branch-and-cut for the forest harvest scheduling subject to clearcut and core area constraints. (English) Zbl 1374.90435
Summary: Integrating forest fragmentation into forest harvest scheduling problems adds substantial complexity to the models and solution techniques. Forest fragmentation leads to shrinking of the core habitat area and to weakening of the inter-habitat connections. In this work, we study forest harvest scheduling problems with constraints on the clearcut area and constraints on the core area. We propose a mixed integer programming formulation where constraints on the clearcut area are the so-called cover constraints while constraints on the core area are new in the literature as far as we know. As the number of constraints can be exponentially large, the model is solved by branch-and-cut, where the spatial constraints are generated only as necessary or not before they are needed. Branch-and-cut was tested on real and hypothetical forest data sets ranging from 45 to 1363 stands and temporal horizons ranging from three to seven periods were employed. Results show that the solutions obtained by the proposed approach are within or slightly above 1% of the optimal solution within three hours at the most.
MSC:
| 90C90 | Applications of mathematical programming |
| 90B35 | Deterministic scheduling theory in operations research |
| 90B90 | Case-oriented studies in operations research |
| 90C10 | Integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C27 | Combinatorial optimization |
References:
| [1] | Baskent, E. Z.; Jordan, G. A., Characterizing spatial structure of forest landscapes, Canadian Journal of Forest Research, 25, 11, 1830-1849 (1995) |
| [2] | Bettinger, P.; Graetz, D.; Boston, K.; Sessions, J.; Chung, W., Eight heuristic planning techniques applied to three increasingly difficult wildlife planning problems, Silva Fennica, 36, 561-584 (2002) |
| [3] | Bettinger, P.; Lennette, M.; Johnson, K. N.; Spies, T. A., A hierarchical spatial framework for forest landscape planning, Ecological Modelling, 182, 25-48 (2005) |
| [4] | Caro, F.; Constantino, M.; Martins, I.; Weintraub, A., A 2-opt tabu search procedure for the multiperiod forest harvesting problem with adjacency, greenup, old grwoth, and even flow constraints, Forest Science, 49, 5, 738-751 (2003) |
| [5] | Carvajal, R.; Constantino, M.; Goycoolea, M.; Vielma, J. P.; Weintraub, A., Imposing connectivity constraints in forest harvest scheduling, Operations Research, 61, 4, 824-836 (2013) · Zbl 1291.90341 |
| [6] | Constantino, M.; Martins, I.; Borges, J. G., A new mixed-integer programming model for harvest scheduling subject to maximum area restrictions, Operations Research, 56, 3, 542-551 (2008) · Zbl 1167.91401 |
| [7] | Elf, M.; Gutwenger, C.; Jünger, M.; Rinaldi, G., Branch-and-cut algorithms for combinatorial optimization and their implementation in ABACUS, (Jünger, M.; Naddef, D., Computational combinatorial optimization - Optimal or probably near-optimal solution (2001), Springer) · Zbl 1052.90106 |
| [8] | Falcão, A.; Borges, J. G., Combining random and systematic search heuristic procedures for solving spatially constrained forest management scheduling models, Forest Science, 48, 3, 608-621 (2002) |
| [9] | Franklin, J. F.; Forman, R. T., Creating landscape patterns by forest cutting, ecological consequences and principles, Landscape Ecology, 1, 1, 5-18 (1987) |
| [10] | Gondran, M.; Minoux, M., Graphs and algorithms (1984), John Wiley & Sons, Inc · Zbl 1117.06010 |
| [11] | Goycoolea, M.; Murray, A. T.; Barahona, F.; Epstein, R.; Weintraub, A., Harvest scheduling subject to maximum area restrictions: Exploring exact approaches, Operations Research, 53, 3, 90-500 (2005) · Zbl 1165.91444 |
| [12] | Goycoolea, M.; Murray, A. T.; Vielma, J. P.; Weintraub, A., Evaluating approaches for solving the area restricted model in harvest scheduling, Forest Science, 55, 2, 149-165 (2009) |
| [13] | Harris, L. D., The fragmented forest: Island biogeography theory and the preservation of biotic diversity (1984), University of Chicago Press: University of Chicago Press Chicago |
| [14] | Hof, J.; Bevers, M.; Joyce, L.; Kent, B., An integer programming approach for spatially and temporally optimizing wildlife populations., Forest Science, 40, 1, 177-191 (1994) |
| [15] | Hoganson, H. M.; Wei, Y.; Hokans, R. H., Integrating spatial objectives into forest plans for Minnesota national forests., (Bevers, M.; Barrett, T., Proceedings of the 2003 symposium on systems analysis in forest resources October 7-9 Stevenson WA, USDA forest service, Rocky mountain research station (2004)) |
| [16] | ILOG (2012). ILOG CPLEX 12.5 - User’s manual.; ILOG (2012). ILOG CPLEX 12.5 - User’s manual. |
| [17] | Könnyũ, N.; Tóth, S., A cutting plane method for solving harvest scheduling models with area restrictions, European Journal of Operations Research, 228, 1, 236-248 (2013) · Zbl 1332.90150 |
| [18] | Kurtilla, M.; Pukkala, T.; Loikkanen, J., The performance of alternative spatial objective types in forest planning calculations: A case for flying squirrel and moose, Forest Ecology and Management, 166, 245-260 (2002) |
| [19] | Martins, I.; Alvelos, F.; Constantino, M., A branch-and-price approach for harvest scheduling subject to maximum area restrictions, Computational Optimization and Applications, 51, 363-385 (2012) · Zbl 1245.90062 |
| [20] | Martins, I.; Constantino, M.; Borges, J. G., Forest management models with spatial structure constraints (1999), C.I.O., Faculty of Sciences, University of Lisbon |
| [21] | Martins, I.; Constantino, M.; Borges, J. G., A branch-and-cut approach for forest management models with spatial constraints (2004), C.I.O., Faculty of Sciences, University of Lisbon |
| [22] | Martins, I.; Constantino, M.; Borges, J. G., 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 (2005) · Zbl 1067.90119 |
| [23] | Martins, I.; Constantino, M.; Borges, J. G., A network flow model for forest management problems with spatial constraints (2005), C.I.O., Faculty of Sciences, University of Lisbon |
| [24] | Martins, I.; Ye, M.; Constantino, M.; Fonseca, M. C.; Cadima, J., Modeling target volume flow in forest harvest scheduling subject to maximum area restrictions, TOP, 28, 343-362 (2014) · Zbl 1298.90049 |
| [25] | McDill, M. E.; Rebain, S. A.; Braze, J., Harvest scheduling with area-based adjacency constraints, Forest Science, 48, 4, 631-642 (2002) |
| [26] | McGarigal, K., Cushman, S. A., & Ene, E. (2012). FRAGSTATS v4: Spatial pattern analysis program for categorical and continuous maps, computer software program produced by the authors at the university of Massachusetts, Amherst. Available at the following web site: http://www.umass.edu/landeco/research/fragstats/fragstats.html; McGarigal, K., Cushman, S. A., & Ene, E. (2012). FRAGSTATS v4: Spatial pattern analysis program for categorical and continuous maps, computer software program produced by the authors at the university of Massachusetts, Amherst. Available at the following web site: http://www.umass.edu/landeco/research/fragstats/fragstats.html |
| [27] | Moreira, J. M.M. A.P.; Rodriguez, L. C.E.; Caixeta-Filho, J. V., An optimization model to integrate forest plantations and connecting corridors, Forest Science, 59, 6, 661-669 (2013) |
| [28] | Neto, T.; Constantino, M.; Martins, I.; Pedroso, J. P., A branch-and-bound procedure for forest harvest scheduling problems addressing aspects of habitat availability, International Transactions in Operational Research, 20, 689-709 (2013) · Zbl 1276.90026 |
| [29] | Neto, T.; Constantino, M.; Martins, I.; Pedroso, J. P., Forest harvest scheduling with clearcut and core area constraints, Annals of Operations Research (2016) · Zbl 1381.90039 |
| [30] | Öhman, K., Creating continuous areas of old forest in long term forest planning, Canadian Journal of Forest Research, 30, 11, 1817-1823 (2000) |
| [31] | Öhman, K.; Eriksson, L. O., The core area concept in forming contiguous areas for long term forest planning, Canadian Journal of Forest Research, 28, 7, 1032-1039 (1998) |
| [32] | Öhman, K.; Lämȧs, T., Reducing forest fragmentation in long-term forest planning by using the shape index, Forest Ecology and Management, 212, 346-357 (2005) |
| [33] | Öhman, K.; Wikström, P., Incorporating aspects of habitat fragmentation into long-term forest planning using mixed integer programming, Forest Ecology and Management, 255, 440-446 (2008) |
| [34] | Rebain, S.; McDill, M. E., Can mature patch constraints mitigate the fragmenting effect of harvest opening size restrictions?, International Transactions in Operational Research, 10, 5, 499-513 (2003) · Zbl 1106.90342 |
| [35] | Rebain, S.; McDill, M. E., A mixed-integer formulation of the minimum patch size problem, Forest Science, 49, 4, 608-618 (2003) · Zbl 1106.90342 |
| [36] | Saunders, D. A.; Hobbs, R. J.; Margules, C. R., Biological consequences of ecosystem fragmentation: A review, Conservation Biology, 5, 18-32 (1991) |
| [37] | Saura, S.; Pascual-Hortal, L., A new habitat availability index to integrate connectivity in landscape conservation planning: comparison with existing indices and application to a case study, Landscape and Urban Planning, 83, 2-3, 91-103 (2007) |
| [38] | Snyder, S.; ReVelle, C., Multiobjective grid packing model: An application in forest management, Location Science, 5, 3, 165-180 (1997) · Zbl 0915.90162 |
| [39] | Tóth, S. F.; McDill, M. E.; George, S., A strengthening procedure for the path formulation of the area-based adjacency problem in harvest scheduling models, Mathematical and Computational Forestry & Natural-Resource Sciences, 4, 1, 27-49 (2012) |
| [40] | Tóth, S. F.; McDill, M. E.; George, S., Testing the use of lazy constraints in solving area-based adjacency formulations of harvest scheduling models, Forest Science, 59, 2, 157-176 (2013) |
| [41] | Tóth, S. F.; McDill, M. E.; Rebain, S., Finding the efficient of a bi-criteria, spatially-explicit, harvest scheduling problem, Forest Science, 52, 1, 93-107 (2006) |
| [42] | Wei, Y.; Hoganson, H. M., Scheduling forest core area production using mixed integer programming, Canadian Journal of Forest Research, 37, 10, 1924-1932 (2006) |
| [43] | Wei, Y.; Hoganson, H. M., Tests of a dynamic programming-based heuristic for scheduling forest core area production over large landscapes, Forest Science, 54, 3, 367-380 (2008) |
| [44] | Williams, J.; ReVelle, C., Reserve assemblage of critical areas: A zero-one programming approach, European Journal of Operations Research, 104, 3, 497-509 (1998) · Zbl 0955.90091 |
| [45] | Wolsey, L. A., Integer programming (1998), John Wiley & Sons, Inc · Zbl 0930.90072 |
| [46] | Yoshimoto, A.; Brodie, J. D., Comparative analysis of algorithms to generate adjacency constraints, Canadian Journal of Forest Research, 24, 1277-1288 (1994) |
| [47] | Zhang, H.; Constantino, M.; Falcão, A., Modeling forest core area with integer programming, Annals of Operations Research, 190, 41-55 (2011) · Zbl 1233.90222 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
