VI ALIO/EURO Workshop on Applied Combinatorial Optimization


December 15 - 17, 2008, Buenos Aires, Argentina




Difficult Combinatorial Problems Arising from Spatial Forest Harvesting Problems

Andres Weintraub

Dep of Industrial Engineering, University of Chile

POB 86-D, Santiago, Chile

Using modeling to support harvesting decisions has been applied successfully for decades. Linear modeling models were used in the 70s with frequency.

As environmental issues became more important, the harvesting models had to incorporate these as spatial issues into the models. One well used statial constraint is reflected as not allowing to harvest blocks beyond a certain limiting area (typically 40 hectares). This can be thought of in a chess board. If a black cell is harvested, you cannot harvest a neighbouring white cell for one or two periods (until the trees in the original black cell have grown to a minimum height). Introducing these constraints into the harvesting models leads to dificult to solve MIPs. In actual use by planners in the 80s and 90s heuristics and metaheuristics were applied. Exact solutions were proposed, which were quite successful in experimental runs. The basic constraints can be thought of as xit+xjt lte 1 if cells i and j are neighbors and xit =1 if cell i is harvested in period t. This formulation is weak, so was replaced by clique formulation, and column generation, were the subproblems corresponded to a stable set problem. The harvesting blocks were constructed by forest engineers using a GIS forming them form basic cells, much smaller than 40 hectares. In the 90s it was shown that by incorporating the forming of the blocks into the models led to siginifcantly better solutions, Again in actual use metaheuristics wree applied. In the 2000s exact models have been proposed. We show several approaches proposed for this latter problem. One form is based on enumerating in some form all possible ways in which a harvesting block may be infeasible and generate those constraints. We have worked on defining all possible feasible blocks and creating constraints that prevent harvesting jointly any pair from being adjacent or overlapping.

This is based on strengthening the formulation by clique-liftingprocedures. Elastisizing constraints linking production between periods also led to improved solutions We discuss these formulations, how they can be made efficient, in particular to solve large size problems. We also discuss how realistic problems include other complicating factors, like considering the need to have large blocks of connected old growth trees. We show computational results, which allow these problems to be solved in real life, and discuss which problems are still open.

This work is shared mainly with Marcos Goycoolea, Juan Pablo Vielma, David Ryan and Alan Murray.