Decompositions and a Matheuristic for a Forest Harvest Scheduling Problem

In this paper, we describe four decomposition models and a matheuristic based on column generation for the forest harvest scheduling problems subject to maximum area restrictions. Each of the four decomposition models can be seen as a Dantzig-Wolfe decomposition of the so-called bucket formulation (compact mixed integer program), in two cases with additional constraints on the connectivity of the buckets. The matheuristic is based on one of the decomposition models (the \(\mathcal{S}\)-knapsack-and-clique decomposition) and relies on the interaction of column generation with a general purpose mixed integer programming solver. We compare the quality of the solutions obtained for benchmark instances with the bucket formulation and with applying column generation and solving the integer restricted master problem (MipHeur) for the same time limit. We concluded that the proposed matheuristic provides, in general, better solutions than both the other approaches for small and medium instances, while, for large instances, the MipHeur approach outperformed the other two.