Search
Local Site Map
Contact Information

Human Dimensions
USDA Forest Service
200 E. Broadway
Missoula, MT 59802

Contact Links


You are here: Human Dimensions / OptFuels Main / Heuristic Solver
OptFuels: Fuel Treatment Optimization

Heuristic Solver

Developing and Analyzing Treatment Alternatives

The heuristic solver employed in OptFuels is designed to develop a number of alternative fuel treatment schedules (solutions), evaluate the cumulative effects of each alternative treatment schedule, and choose the best fuel treatment schedule that produces maximum treatment effects (minimize overall expected loss) over time while meeting given resource and operational constraints. Figure 1 provides an overview of the implementation of the heuristic solver within the OptFuels system. The solver includes a subroutine to develop FlamMap landscape (LCP) files that represent vegetation and fuels attributes in each time period as treatment effects. Through the use of dynamic link libraries (DLLs), the solver automatically runs the MTT algorithm on each LCP file and stores the outputs (i.e., flame length and fire arrival time in each pixel) for solution evaluation. Each solution is evaluated as the sum of expected loss value of a given study landscape over time (Equation 1). Expected loss value in each pixel depends on user-defined relative value of the pixel and burn probability, and estimated flame length and fire arrival time retrieved from the MTT output.

Optfuels Heuristic Solver Logic

hs_equation[Eq.1]

Where:

  • f is an index of flame length category
  • c is an index of grid cells (pixels)
  • t is a time period
  • Lossf,c,t is an expected loss value of grid cell c at flame length category f in time period t
  • Yf,c,t is a binary variable indicating the flame length category of cell c in period t
  • Pc,t is a probability of cell c being burn by given fire scenarios (fire ignition locations and durations) in time period t

A simulated annealing (SA) algorithm is employed in the solver for the optimization engine. Simulated Annealing (SA) is a heuristic search technique that has been widely used to solve large combinatorial problems in various fields (Kirkpatrick and others 1983). The ideas that form the basis for SA were first published by Metropolis and others (1953) in an algorithm to simulate the cooling of materials in a heat bath - a process known as annealing. The approach is a Monte Carlo method that uses a local search in which a subset of solutions is explored by moving from one solution to a neighboring solution. To avoid becoming trapped in a local optimum, the procedure provides for an occasional acceptance of an inferior solution to allow it to move away from a local optimum. The SA algorithm employed in the heuristic solver is briefly explained below and illustrated in Figure 2. Any combinations of budget and acreage constraints can be considered during the optimization process.

The Heuristic Solver Process

Basic Steps

  1. Develop and evaluate an initial solution (no action). Store the solution as the current solution.
  2. Create a new solution by slightly modifying the current solution (randomly select a set of treatment polygons and assign new fuel treatment options other than no action).
  3. Check the feasibility of the new solution. If the solution violates any of the constraints, discard the solution and go back to Step 2. Otherwise, go to Step 4.
  4. Accept or discard the new solution based on the SA solution acceptance rule.
  5. Go to Step 2 until predefined stopping criterion (i.e., ending temperature) is met.

The heuristic solver uses a GIS layer of stand polygons to assign fuel treatments. Because treating individual stands is generally not effective at changing fire behavior at the landscape scale (Finney 2006), stands are clustered by the solver to serve as the treatment units. This is accomplished by developing clusters of adjacent polygons with the same available treatment type and period. A cluster is generated by randomly selecting an unassigned polygon and an available treatment for that polygon other than no action (treatment type and period). Then, an unassigned adjacent polygon to the seed polygon with the same available treatment is randomly selected, and the cluster's area is updated. The process of adding unassigned adjacent polygons continues until the target cluster size is achieved.

Phases

The selection of treatments and treatment clusters to develop alternative solutions is done in two phases.

Phase One

The solver starts with a "no action" solution as iteration zero (i = 0), solution feasibility and penalty are evaluated, FlamMap and the MTT algorithm are run for each period, and expected loss is calculated. For the first iteration (i = 1), a cluster of adjacent polygons is randomly located within the treatment area. Then solution feasibility is evaluated, FlamMap and the MTT algorithm are run, and expected loss is calculated. For the next iteration (i = 2), another cluster is randomly located within the treatment area. Again, feasibility is evaluated, FlamMap and the MTT algorithm are run, and expected loss is calculated. The treatment options are screened to have a desirable effect in altering fire behavior; smaller flame lengths (m) and/or slower spread rates. Consequently, as the solver iteratively places clusters, expected loss decreases, and the associated penalty associated with any lower limit constraints also decreases as the solution attributes (i.e., acreage, costs, etc.) approach the lower limit of these constraints. When penalty reaches zero, the lower limits of the set of constraints are exceeded, and solutions become feasible. The solver stops adding additional clusters when solutions become infeasible because the upper limit of one or constraint is exceeded. This indicates the maximum area feasible to treat for each period has been reached.

Phase Two

During phase two, the solver improves the random allocation of clusters assigned during phase one by iteratively changing the location of treatments, one cluster at a time. At each iteration, a previously selected cluster is randomly selected for removal from current solution. This means, the selected treatment (type and period) for the stand polygons in that cluster are changed to no action. Then, another cluster is randomly selected and solution feasibility is evaluated. If the solution is infeasible, the new cluster location is ignored and another random cluster location is generated. If the solution is feasible, then FlamMap and the MTT algorithm are run, and expected loss is evaluated. During phase two, only feasible solutions are considered, and the solver continues changing the location of single clusters at each iteration. The process stops when the simulated annealing ending temperature is reached, the stopping rule for SA.

Implementation of the Heuristic Solver

In order to implement the SA search process, several control parameters need to be set. These include beginning and ending temperatures, repetitions at each temperature level, and temperature cooling rate. The OptFuels interface provides three options with pre-set parameter values to choose from: low intensity, medium intensity, high intensity, as well as a custom option where users can define values for each parameter. The higher intensity option runs more iterations and thus can likely provide a better solution than the other two lower intensity search options, but requires a larger amount of computation time.

Run time

Test runs of the initial version of the solver indicated that the solver required a considerable amount of computation time due to the fire simulation process by MTT and the complexity of spatial and temporal scheduling problems. To improve the efficiency of the solution process, the current version of the heuristic solver was designed for multi-threading and multi-processing using OpenMP with Visual C++. As a result, the solver can now simultaneously run MTT for multiple time periods, and the computation time can be significantly reduced. For example, using an 8-processor computer, the solver takes about 30 seconds to locate treatments within the landscape and run FlamMap and the MTT algorithm for a 3-period problem over an area of about 20,000 acres using a 90-meter cell resolution. Based on the respective SA parameters, the solver takes about 4 hours, 25 hours, and 8 days to find best allocation and schedule of fuel treatments under the low, medium, and high intensity options, respectively.

Last Modified on: March 23, 2011