Spatial Forest Planning with Integer Programming Lecture 10 (5/8/2017) Spatial Forest Planning Spatial Forest Planning with Roads Balancing the Age-class Distribution Forest Age Class Distribution 50K A cres 40K Red Oak Red Maple Other Zones Other Oaks Other Hrdwds. N. Hrdwds. Conifers A. Hrdwds.

30K 20K 10K 0K Forest Age Class Distribution 28K 24K A cres 20K 16K 12K 8K 4K 0K Red Oak Red Maple Other Zones Other Oaks Other Hrdwds. N. Hrdwds. Conifers

A. Hrdwds. Spatially-explicit Harvest Scheduling Models Set of management units T planning periods Decision: whether and when to harvest management units Modeled with 0-1 variables xmt = 1 if unit m is harvested in period t, 0 otherwise Spatially-explicit Harvest Scheduling Models (continued) Constraints Logical: can only harvest a unit once, at most Harvest volume, area and revenue flow control Ending conditions Minimum average ending age Extended rotations Target ending inventories Maximum harvest area (green-up) Others spatial concerns: Roads, mature patches, etc Integer Programming Model for Spatial Forest Planning

M T MaxZ Am [cm 0 xm 0 cmt xmt ] m 1 t hm subject to: T xm 0 xmt 1 one constraint for each m=1,2,,M t hm vmt Am xmt H t 0 one constraint for each t=1,2,,T mM ht bl ,t H t H t 1 0

one constraint for each t=1,2,,T-1 bh ,t H t H t 1 0 one constraint for each t=1,2,,T-1 x one constraint for each C and for each t=hi,,T jt C 1 jC M T T T Am [( Age Age ) xm0 ( AgemtT Age ) xmt ] 0 m 1 xmt 0,1

T m0 t hm for each m=1,2,,M and for each t=1,2,,T Notation where hm = the first period in which management unit m is old enough to be harvested, xmt = a binary variable whose value is 1 if management unit m is to be harvested in period t for t = hm, ... T; when t = 0, the value of the binary variable is 1 if management unit m is not harvested at all during the planning horizon (i.e., xm0 represents the do-nothing alternative for management unit m), M = the number of management units in the forest, T = the number of periods in the planning horizon, cmt = the net discounted net revenue per hectare plus the discounted expected forest value at the end of the planning horizon if management unit m is harvested in period t, Mht = the set of management units that are old enough to be harvested in period t, Am = the area of management unit m in hectares, vmt = the volume of sawtimber in m3/ha harvested from management unit m if it is harvested in period t, Ht = the total volume of sawtimber in m3 harvested in period t, Notation cont. and

bl,t = a lower bound on decreases in the harvest level between periods t and t+1 (where, for example, bl,t = 1 would require non-declining harvests and bl,t = 0.9 would allow a decrease of up to 10%), bh,t = an upper bound on increases in the harvest level between periods t and t+1 (where bh,t = 1 would allow no increase in the harvest level and bh,t = 1.1 would allow an increase of up to 10%), C = the set of indexes corresponding to the management units in cover C, = the set of covers that arise from the problem, hi = the first period in which the youngest management unit in cover i is old enough to be harvested, T Agemt = the age of management unit m at the end of the planning horizon if it is harvested in period t; and T Age = the minimum average age of the forest at the end of the planning horizon. The Challenge of Solving SpatiallyExplicit Forest Management Models Formulations involve many binary (0-1) decision variables Feasible region is not convex, or even continuous In fact, it is a potentially immense set of points in n-dimensional space Solution times could increase more than exponentially with problem size 1.) Unit Restriction Model (URM):

adjacent units cannot be cut simultaneously 2.) Area Restriction Model (ARM): adjacent units can be cut simultaneously as long as their combined area doesnt exceed the maximum harvest opening size Pair-wise Constraints for URM Adjacency list: F, 4 AB D, 8 AD B, 4 C, 10 A, 14 AE E, 7 BC BD Pair-wise adjacency constraint for AB BE is CD DF x A t x B t 1

What is a better formulation? Maximal Clique Constraints for URM Maximal clique list: ABD ABE BCD DF F, 4 D, 8 B, 4 A, 14 C, 10 E, 7 Clique adjacency constraint for ABD is x A t x B t x Dt 1 Cover Constraints for ARM Cover list:

ABC AD BCD AE BCE BDEF CDF Amax 20ha F, 4 D, 8 B, 4 A, 14 C, 10 E, 7 Cover constraint for FDC is: xC t x D t x F t 2 In general: xmt C 1 mC McDill et al. 2002

GMU Constraints for ARM GMU list: Amax 20ha F, 4 A-F D, 8 AB B, 4 C, 10 A, 14 BC E, 7 BD BDE GMU variable for BDF is: x BDF t BDF xnt 1 j J and t h j , ..., T The constraint BE nK in general form: CD K jtis the set of GMUs that contain at le Where

one stand in max clique j; CF jt J is the set of max cliques; and hj is the first period in which the young stand in clique j is old enough to be McDill et al. 2002 and Goycoolea et al. 20 The Bucket Formulation of ARM Introduce a class of clearcuts: , and it Introduce variables xm that take the value of 1 if management unit m is assigned to clearcut i in period t. Objective function: M T MaxZ am [cm 0 xmi 0 cmt xmit ] m 1i t hm Constantino et al. 2008

The Bucket Formulation of ARM (cont.) Constraints: T it x m 1 for m = 1, 2, ..., M t 0,t hm i M it a x m m Amax for i and t = hm, . . . T it m

for Q , m Q, i m and t = hm, . . . T m 1 it Q x w it Q w 1 i for Q and t = hm, . . . T The Bucket Formulation of ARM (cont.) Constraints: vmt am xmit H t 0 for t = 1, 2, . . . T

mM ht , i bl ,t H t H t 1 0 for t = 1, 2, . . . T-1 bh ,t H t H t 1 0 M T i0 m T t hm T mt T it a [( Age Age

) x ( Age Age ) x m m ] 0 i m 1 T m0 The Bucket Formulation of ARM (cont.) it Q w takes the value of one whenever a unit in maximal clique Q is assigned to clearcut i in period t; Q is a maximal clique in the set of maximal cliques.

Strengthening and Lifting Covers x13 x14 x43 x50 2 x3 3 x13 x14 x43 x50 3 x24 x38 1 x24 x38 x3 1 x24 x38 x49 1 x18 x31 x40 2 x18 x31 x40 x6 x15 2 x18 x31 x40 x8 2 Amax 48ha Formalization minimal cover constraint has the general form of: x C 1 j jC

where C is a set of management units (nodes) that form a connected sub-graph of the underlying adjacency graph, and for which a j Amax a j Amaxholds, but jC for any l C. jC \ l maximum harvest area area of unit j Strengthening the Minimal Covers Notation:denote Let the set of all possible minimal covers tha arise from a certain forest planning problem (or adjacency graph). Number of units in the forest Define: P {x {0,1}n :

iC xi C 1, C }. ( Arepresent ) For every set of management units A,N let the set of all management units adjacent, but not belonging, to A. Define: ( s, C ) max{ jN ( s )C x j : x P and x s 1} Strengthening the Minimal Covers Cont. ( s, C ) max{ jN ( s )C x j : x P and x s 1} andC s N (C ). Proposition: Consider a minimal cover Define: * N ( s) C ( s, C ) 1 . Then, for all *: x jC j xs C 1is valid for P.

Strengthening the Minimal Covers Cont. 0 the inequality holds by the then Proof: Considerx P. If xs , definition of minimal cover C. If xs 1, then: x jC j xs xj jC \ N ( s ) C \ N (s) x j

x j * jN ( s ) C jN ( s ) C C \ N ( s ) ( s, C ) * C 1 * N ( s) C ( s, C ) 1 How strong are these inequalities? s 2ha Amax 3ha 1 1ha 2 3 1ha 1ha 4 * N ( s ) C ( s, C ) 1 1ha

1ha x1 x2 x3 x4 3 x1 x2 x3 x4 1xs 3 x1 x2 x3 x4 2 xs 3 Sequential Lifting Algorithm Strengthening and lifting [1] Generate the set of minimal covers, using the Path Algorithm Pick a cover, C from set . [2] [1] Generate the set of management units, S that are adjacent to at least 2 units of C. [3] Pick a unit, s from set S. [4] Determine * using s

Proposition 1. [6] NO S ? S S \{s} YES YES Build E(C) YES [7] [8] [9] s* 1 ? [5] QC ?

YES QC QC {s} NO QC 1 YES NO For s QC , set Solve NO s s* i QC ? PA,C . NO [12] YES

Build E(C) YES PA,C C 1? NO i 0? i=j=1 [10] i =i+1 NO [11] 1. 1 i i 2. t j i 3. j j 1 NO i 0? YES

[13] k 0 YES [14] s s* ? kQs \{ s } for an s QC ? YES [15] [17] NO Solve PA,C . [18] NO

PA,C C 1? YES Build E(C) [16] 1. i t j 2. i i 1 3. j j 1 [19] Build E(C) [20] i QC ? [21] NO [23] \{C} NO [22] NO YES

s sQC QC . NO s* ? sQC YES [24] ? YES STOP Compatibility testing Open Questions: 1) Can one define a rule for multiple lifting? 2) Can one find even stronger

inequalities? 3) Is there a better formulation? A Cutting Plane Algorithm for the Cover Formulation X 8 X18 X 40 2 X 21 X 37 X 47 2