Strategic planning of preparedness budgets for wildland fire management

Forest fires in the United States consume more than five million acres of land and result in extensive loss of life, property, and natural resources. Furthermore, the federal government spends, on average, $800 million each year to contain the fires. The deployment of firefighting resources required to contain the fires (such as engines, bulldozers, and helicopters) poses an immense challenge because of the large number of resources, the unique requirements of each geographical location, the multitude of resources available to fight the fires, and the varying staffing level associated with each resource. The issue is further complicated because several agencies with different interests and responsibilities manage the federal lands, including the USDA (United States Department of Agriculture) Forest Service, Bureau of Land Management, Bureau of Indian Affairs, National Park Service, and U.S. Fish and Wildlife Service. In the past, each agency has used planning analysis models and systems to determine the desired staffing and budget required for wildland fire-management programs. Most of these systems rely on economic theory that has played a fundamental role in wildland fire management since Headley [1] and Sparhawk [2] described tradeoffs involved in establishing an optimal wildfire management program. The theoretical framework used to identify the most economically efficient level of fire management expenditures has been the Cost Plus Net Value Change model (C+NVC) [3], which minimizes the cost of wildland fire management by minimizing the sum of the preparedness cost (expenditures associated with preparation for a fire season), suppression cost (direct wildfire-suppression expenditures during a fire season), and NVC (net wildfire damages). However, the C+NVC model does not specify the strategies for deployment of firefighting resources that are necessary to achieve the minimum cost. For a model to be of operational value, the solution must indicate the specific resource deployment plan for any given wildfire and the corresponding total budget requirement.

By using the C+NVC model, the USDA Forest Service developed the National Fire Management Analysis System (NFMAS), the first operational system in the United States that computes the most efficient deployment of firefighting resources. NFMAS allows its users (wildfire management analysts and planners) to choose firefighting resources, resource dispatch rules, and preparedness budgets; it then calculates the predicted corresponding costs and damages for a given geographical area and set of fire conditions. The user may systematically change these input parameters in an attempt to arrive at the best resource deployment plan that minimizes the sum of the total cost and the net wildfire damages. However, because NFMAS is a simulation model and relies on the user to determine the optimal strategy through trial and error, it cannot always reliably identify the optimal resource deployment strategy.

Other systems that are not based on criteria as broad as those of NFMAS have also been developed. For example, the CFES–IAM model [4] was developed for the California Division of Forestry. It does not directly consider the economic costs of wildfire damages, but rather implements a California legislative mandate to provide equal protection for lands of equal value. The National Park Service uses a fire management model called FIREPRO that was not designed to consider the relative utility of firefighting resources, which we often refer to as the “value” of such resources, or to solve for the optimal deployment of firefighting resources.

As we have just noted, government agencies use different systems to estimate their program needs, including preparedness resource planning, yet no one system has been able to adapt to the increasing complexity of fire management. These challenges resulted in the need for the standard, automated, interagency Fire Program Analysis (FPA) system, with a preparedness module (PM) as part of a first phase for fire preparedness resource planning. Central to this resource planning process is a linear optimization (mixed-integer programming) model that maximizes acres managed for a given level of cost. The model is solved iteratively across a range of total cost constraints in order to establish a function that maps the best achievable effectiveness, in terms of acres managed, for each cost level in that range. An interpretation of the mapping may provide a funding authority with the means to select from a menu of cost-efficient alternatives. A function known as the effectiveness frontier indicates the amount of fire protection that can be obtained at different levels of appropriation and empowers the appropriator to make informed decisions regarding alternative program levels.

The body of this paper covers the background, formulation, and solution approach to the resource planning problem in the FPA project. Following the solution approach, we examine the modeling challenges, present computational results and analyses, and discuss our efforts in validating the model. Finally, the impact of our work is summarized and some future directions are discussed.

The strategic planning model for FPA–PM is a mixed-integer program that optimally deploys firefighting resources to maximize acres managed for a specified cost level. This is done in a way that allows the generated budgets to be accumulated nationally for program analysis and budget requests. The scope may be considered strategic in nature, and the model does address the tactics of resource deployment at the operational level, such as the specific sequence of resource deployment. The model is a direct extension of the one developed by Rideout and Kirsch [5], which is referred to as the original model in this paper.

The model addresses the response requirements for two types of fires, each entailing a different response strategy. Initial response fires require suppression in the first 18 hours. Wildland fire use (WFU) fires [6] have a defined management and workload associated with monitoring the fire. WFU fires are fires proactively set by fire planning units in order to reduce hazardous conditions at locations that may result in a potential fire in the future. The fire management team identifies such locations and performs a controlled burning to eliminate the hazardous conditions. Since these fires are set intentionally by the firefighting crew, each fire has an estimated management and monitoring workload. Correspondingly, each resource that can be deployed to the WFU fire has two numerical values, one associated with the management capability and the other with the monitoring capability.

To help capture the variance in potential fire effects across a fire season (i.e., a year) and across geographical regions known as fire planning units, or FPUs (and therefore to help capture the potential impact on natural, cultural, and social resources), the year is divided into 26 two-week blocks called sensitivity periods. Two-week periods are proposed as the minimum resolution needed to capture the most important temporal differences in fire effects on land management values. (The term land management values relates to such factors as keeping air and water clean, sustaining rural forest and economic development, improving forest health, restoring ecological balance, and enhancing wildlife habitat and population). For any given FPU that requires a budgeting analysis, a set of representative fires—distributed throughout the FPU over the sensitivity periods—are generated in our model on the basis of historical fire data. A weight is assigned to each representative fire to reflect the differences in the management values of the land burned by that fire. Unless otherwise noted in the paper, representative fires are simply referred to as “fires.”

Each type of firefighting resource has an associated fireline production rate (rate of dissipation of fire retardants), preparedness cost (fixed cost), and utilization cost (deployment cost). Many restrictions exist on the use of fire resources within FPUs. A significant consideration in determining an initial response to an unplanned ignition must take into account the fire equipment or strategies that may be applied to a particular place. This consideration must incorporate agency-specific policy, ensure compliance with applicable laws and legislation, and provide protection for sensitive resources from potentially damaging fire operations. Each resource may also have operational constraints placed on its use that are unrelated to management objectives. A constraint in this context relates to the operational capability of a particular piece of equipment to perform under the necessary conditions. Examples include constraining the use of a helicopter at high elevations if it is not rated for high-altitude missions, or constraining the use of a bulldozer on slopes that exceed the general capabilities for that piece of equipment.

Containment of a fire is achieved if the sum of the firelines constructed is at least equal to the fire perimeter at any time for a given total cost. If the model is unable to contain a fire within its cost allotment, the fire is assumed to have escaped the initial response. The size and cost of an escaped fire are estimated from statistical analysis of historical fire and weather data. Given a total cost constraint, the integer program deploys firefighting resources in an attempt to contain the fires while maximizing the number of weighted acres managed (WAM), a measurement of overall fire management effectiveness. WAM is defined as the sum of individual fire management effectiveness over all of the fires in an FPU. For each fire, the management effectiveness is calculated by multiplying acres managed by the weight of the fire. (The term weight is used to indicate the relative importance of fires and is affected by characteristics such as human and animal population density.)

In summary, given a set of fires and available resources in an FPU, the optimization model

1. Maximizes the WAM.
2. Enforces fire containment constraints that determine the final fire sizes.
3. Enforces the total budget constraint (i.e., the total of preparedness and suppression costs).

Each execution of the optimization model determines a single point on the effectiveness frontier. Each point represents a combination of total cost and the effectiveness that it can attain as measured by WAM. The entire effectiveness frontier is mapped by iteratively executing the optimization model across cost levels. Mapping the effectiveness frontier allows the budget planners to determine, for each FPU, the preparedness staffing needs, the associated effectiveness, and the number of acres that would be expected to burn for a given budget level. Additionally, the model data for each FPU and its corresponding model results (the entire effectiveness frontier) populate the national FPA database for all of the planning units in the nation. This allows the national budget planners to assess tradeoffs among planning units nationwide.

In this section, we describe the notation used in order to present the model. We also list certain characteristics that are central to the model formulation. We then provide the actual formulation and its detailed explanation.

Time parameters

Ti	Maximum time (in minutes) considered for initial response to fire i.
Ti0	Time at which fire i is considered to have escaped; Ti0 is set to (Ti + 1). (For example, the escape time of the fire is one minute more than the maximum containment time Ti.)

Fire parameters

I	Set of all representative fires to be managed for the year, indexed using i.
J	Set of unique fire groups, indexed using j. A fire group is a collection of simultaneous fires.
IjS	Set of unique initial response fires in fire group j.
IjW	Set of unique WFU fires in fire group j (IjS ∪ IjW = Ij).
Wi	Importance (i.e., weight) given to a land burned by fire i.
PiD	Initial perimeter (in chains) of fire i at time zero (t = 0), when the fire is discovered. A chain is a unit of measure in land surveys (80 chains = 1 mile).
Pi(t)	Perimeter growth piecewise-linear (PWL) function of fire i.
Pi	Total perimeter of fire i at time Ti.
Pi0	Total perimeter of escaped fire i at time Ti0.
AiD	Initial area burned (in acres) by fire i at time zero, when the fire is discovered.
Ai(t)	Area growth PWL function of fire i.
Ai	Total area burned by fire i at time Ti.
Ai0	Total area burned by escaped fire i at time Ti0.
TiG	Total growth or burning time of fire i.
WLiG	Management workload for WFU fire i.
WLiT	Monitoring workload for WFU fire i.
MirG	Management capability of resource r on WFU fire i, where i ∈ IjW.
MirT	Monitoring capability of resource r on WFU fire i, where i ∈ IjW.

Resource parameters

R	Set of all potential firefighting resources, indexed using r.
Ru	Set of resources that must be utilized, where Ru ⊆ R.
Ri	Set of all resources that may be deployed to fire i, where Ri ⊆ R.
Ir	When IR is defined as equal to ∑i∈I |Ri|, IR is the set of all fires that may be contained using resource r, where Ir ⊆ I.
RWT	Set of all water tenders, where RWT ⊆ R.
RiWT	Set of water tenders that may be deployed to fire i, i.e., RiWT = RWT ∩ Ri.
R(W)	Set of resources (engines) that can be supported by a water tender, where R(W) ⊆ R.
Ri(W)	Set of resources in R(W) that may be deployed to fire i, i.e., Ri(W) = R(W) ∩ Ri.
RiGR	Set of all ground resources that may be deployed to fire i, where RiGR ⊆ Ri ⊆ R.
RiAT	Set of all air tankers that may be deployed to fire i, where RiAT ⊆ Ri ⊆ R.
Tira	Arrival time of resource r on fire i.
Tird	Departure time of resource r from fire i.
Qir(t)	Fireline production PWL function by resource r when containing fire i.
∇Qir(t)	Additional fireline production PWL function of resource r when supported by a water tender in containing fire i.
K	Maximum number of air tankers that one ground resource can support.

Fixed and variable cost parameters

TC	Total cost ceiling (preparedness plus suppression costs) for initial response.
Fr	Fixed cost for using a resource r ∈ R.
Ci	Partial suppression costs of fighting escaped fire i incurred during initial response.
Di(t)	Resource-independent suppression cost PWL function for fighting contained fire i.
DiD	Resource-independent suppression cost at the time of discovery of fire i.
Hir	Total variable cost for using resource r in suppressing fire i at time Ti.
Hir(t)	Hourly cost PWL function for using resource r in suppressing fire i.

Penalty cost parameters

P	Set of overhead resource groups, indexed using p. Each overhead resource group is a collection of resources in a corresponding program leadership group. (Overhead resource groups share common characteristics, such as belonging to a certain resource type or dispatch location or having similar training program requirements. A program leadership group comprises a set of resources requiring the same training program for improving their effectiveness.)
S	Set of station resource groups, indexed using s. Each station resource group is a collection of resources stationed at the same dispatch location.
E	Set of equipment resource groups, indexed using e. Each equipment resource group is a collection of resources of the same type, e.g., engines or helicopters.
Rp	Set of resources in overhead group p, where Rp ⊆ R.
Rs	Set of resources in station group s, where Rs ⊆ R.
Re	Set of resources in equipment group e, where Re ⊆ R.
THp	Threshold quantity of overhead group p beyond which acquisition penalties are incurred. (Acquiring resources beyond the threshold limit accrues a penalty cost.)
Gp	Penalty cost of using resources of overhead group p beyond the threshold quantity THp.
Vsn	Penalty cost of using n resources at dispatch location s, where 0 ≤ n ≤ |Rs|.
THe	Threshold quantity of type-e resources beyond which acquisition penalties are incurred.
Oe	Unit penalty cost of using resources of type e beyond the threshold quantity THe.

Objective parameters

B	Total number of weighted acres burned (WAB).
W(0)	Total WAB if no containment action is taken.
W	Total WAM by initial response, i.e., W = W(0) − B.

In the previous section, we listed parameters—that is, various entities that correspond to the input data used in defining the model inputs. They define the characteristics of the model. In this section, we list variables or decision variables. These entities define the unknown values for which an optimal value is desired. All variables in our model are denoted in lower case.

In the previous sections we listed various parameters and variables. Here we provide a list of notes that further elucidate the meaning of some of these entities.

• The optimization model aims at allocating resources to a set of deterministic, representative fires for which there is perfect a priori knowledge for the entire planning horizon.

• T_i is the maximum time during which the resources can fight a fire i. A fire that escapes has a duration of (T_i + 1), also denoted as T_i⁰.

• Both resource-deployment and fire-burning durations are measured on the same time scale t between 0 and T_i, which denotes the time elapsed after a fire event is reported at time zero.

• Initial response fires can be contained either during daytime or nighttime. This delineation is required, since during nighttime the fires do not grow in size. Hence d_i^f = 1 if fire is contained during daytime and n_i^f = 1 for fires contained at night.

• The total fire perimeter P_i and the total area burned A_i are defined for all fires. Escaped fires, i.e., fires with d_i^f = n_i^f = 0, are assigned a final perimeter P_i⁰ and an area A_i⁰.

• Fire-suppression resources include attributes that may limit their use in specific FPUs. This requirement is implemented by introducing sets R_i and I_r.

• No resource is deployed to an uncontained fire. This requirement was mandated by subject matter experts, because any fire that escapes the initial attack will be handled in a large-fire optimization. (The initial attack is the process of fighting the fire for 18 hours or until the fire covers more than 300 acres.)

• Simultaneous fires (concurrent fires) in one fire group compete for exclusive use of initial response resources; in other words, if a resource is deployed to one fire, it cannot be deployed to any other fires in the same fire group.

• Resource arrival times are accounted for in the fireline production rates (rates of dissipation of fire retardants). By adjusting the production rates in the same manner, one can account for decreases in production caused by fatigue or refill times.

• Fire-containment costs comprise fixed resource costs F_r (also known as preparedness costs) and variable suppression costs, which in turn are composed of resource-independent suppression costs D_i(t) (also known as mop-up costs) and resource-dependent suppression costs H_ir(t). Mop-up costs are the costs associated with cleanup after a fire has been contained.

• Fixed resource costs are incurred if a resource is deployed as a result of the optimization. However, fixed resource costs are incurred for all resources in set R_u (must-use resources that usually have already been paid for) whether or not they are deployed.

• Various penalty costs (e.g., overhead, station, and equipment costs) associated with an optimal resource organization should be accounted for within the optimal model to ensure the optimality of the solution. Applying penalty costs in the post-optimization phase is not guaranteed to preserve optimality of the solution. This requirement is implemented by introducing new variables g_p, v_sn, and o_e, and corresponding penalty cost parameters G_p, V_sn, and O_e. Note that overhead costs refer to nondeployment-related costs associated with acquiring additional resources above a threshold number. These overhead costs are applied to a group of resources belonging to a certain resource type, dispatch location, or training program requirement.

• The penalty cost associated with any overhead resource group p is a constant (G_p); it is independent of number of resources n, for n > TH_p ≥ 0, and is zero for 0 ≤ n ≤ TH_p.

• The penalty cost associated with any resource group of type e is linear in the number of resources n, for n > TH_e ≥ 0, and the cost is zero for 0 ≤ n ≤ TH_e.

The optimization model may be presented as shown in the equations that follow. The meaning of each equation in this global problem optimization (GPO) is given in the section on formulation details.

(1)

(2)

Tirduir ≥ ur     ∀i ∈ I, ∀r ∈ Ri,

(3)

Tirauir ≤ ur     ∀i ∈ I, ∀r ∈ Ri,

(4)

(5)

(6)

dif + nif ≤ 1     ∀i ∈ I,

(7)

tid ≤ TiGdif     ∀i ∈ I,

(8)

tin ≤ Ti0nif     ∀i ∈ I,

(9)

(10)

dif + nif ≤ 0    ∀r ∈ RiGR, RiGR ∩ Ri = Ø,

(11)

(12)

lirw ≤ ∇Qir(Tir0)uir    ∀i ∈ I, r ∈ Ri(W),

(13)

lirw ≤ 0     ∀r ∈ RiWT, RiWT ∩ Ri = Ø,

(14)

yr = 1     ∀r ∈ Ru,

(15)

dir ≥ Hir(uir)    ∀i ∈ I, ∀r ∈ Ri,

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

A detailed explanation of the objective function [Equation (1)] and each constraint [Equations (2)–(24)] listed in the formulation in the previous section is provided below:

1. The objective of the FPA model is to maximize the WAM. Conversely, the model attempts to minimize the weighted acres burned (WAB). The WAB for each fire is the product of the weight assigned to the fire and the final fire size. It is also subject to the containment or escape of the fire. For fires contained during daytime, the WAB is the sum of the discovery size and size of the fire until the time at which containment is achieved. For fires contained during nighttime, the WAB is a sum of the discovery size and the size of the fire until nightfall. The size of the fires that escape the initial attack is defined as the escape size.

2. Each resource deployed to a fire must remain deployed until containment is achieved. Hence, the containment duration of the fire is greater than or equal to the deployment duration of the resources.

3. A resource cannot be deployed after the departure time of the resource. This is relevant for aerial resources that cannot fight fire during nighttime.

4. A resource can be deployed only after the arrival time of the fire.

5. A fire is said to be successfully contained if the total line produced by all deployed resources is greater than or equal to the perimeter of the fire at the containment duration. If the resource organization contains engines and water tenders, additional line production capability of engines in the presence of water tenders is also taken into account.

6. The resource binary variable should be set to 1 for each resource that has been deployed to a fire.

7. The fire can be contained either during daytime or nighttime.

8. If a fire is contained during daytime, the containment time should be less than or equal to the nighttime.

9. If a fire is contained during nighttime, the containment time should be less than or equal to the nighttime end time of the fire.

10. Each ground resource deployed to a fire must remain deployed until the fire is contained.

11. A fire cannot be contained in the absence of a ground resource. This policy is adopted by firefighters in the field to enable verification of containment by a ground crew if aerial resources are used to contain the fires.

12. The maximum additional line production capacity of an engine resource in the presence of a water tender is less than or equal to the product of the additional line production rate of the engine resource and the number of water tender resources deployed to the fire.

13. The maximum additional line production capacity of an engine resource in the presence of a water tender is less than or equal to the maximum line production capacity of the resource until the maximum deployment duration of the resource.

14. The additional line production of an engine resource is zero in the absence of a water tender.

15. Any must-use resource must form a part of the resource organization (even if it is not deployed to any fire).

16. The deployment cost of a resource is greater than or equal to the product of the deployment cost function and the deployment duration of the resource.

17. The sum total of management capability of all deployed resources is greater than or equal to the management workload required for the fire.

18. The sum total of the monitoring capability of all deployed resources is greater than or equal to the monitoring workload required for the fire.

19. The resources in the overhead resource group must be accounted for.

20. The total number of resources deployed from an overhead group cannot exceed the overhead group threshold limit.

21. The resources deployed from each dispatch location must be accounted for.

22. If a resource has been deployed from a dispatch location, the dispatch location flag must be activated.

23. The total penalty cost for deploying more resources than the penalty group threshold is greater than or equal to the product of the penalty cost per resource and the number of resources deployed from that penalty group.

24. The total cost of resource organization (fixed and deployment cost, fire-suppression cost, and leadership, station, and equipment penalty cost) should be less than or equal to the budget cost.

The optimization model formulated in the previous section implicitly addresses two different problems: resource acquisition, which deals with the problem of generating the feasible initial response organization, and resource deployment, which evaluates the maximum effectiveness for a given proposal for an initial response organization, within allowed budgets. While the resource acquisition component of the model is fairly compact, the deployment problem is associated with details pertaining to numerous combinations of resources, fires, and deployment time periods. Solving the global model as is proves difficult and in most cases impossible because of the computationally prohibitive size of the model instances (especially for large FPUs) and the intrinsic runtime complexity that arises from low-level resource deployment decision-making.

Analysis of preliminary optimization results and available historical data reveals that resource acquisition is the overarching factor in the model because, on average, the resource acquisition cost (fixed cost plus various penalty costs) makes up more than 80% of the total initial response cost. Therefore, we devised a solution approach that is based on a two-phase decomposition crash heuristic (DCH).

Resource deployment problem (RDP)
The first phase is formulated as a cost-unconstrained resource deployment problem, which makes use of the previously presented set of equations in the GPO without the cost constraints in Equations (19)–(24).

Resource acquisition problem (RAP)
The second phase is formulated as a resource acquisition problem that involves deciding which fire(s) to let escape and which proposed resource(s) to give up so that the original cost constraint can be satisfied, given Equations (19)–(23) and with

(25)

and

(26)

The new parameters and decision variables introduced in RAP are defined as

The solutions resulting from the two subproblems are then combined to construct a feasible integer solution to hot-start the original mixed-integer programming instance. Note that providing a feasible solution as a starting point for an optimization problem is referred to as “hot-starting” an optimization; this enables the optimizer to search for alternate solutions that result in an improvement in the objective function, thereby reducing the solution time. Specifically, the solution to the RDP gives values corresponding to fire containment (d_i^f, n_i^f), resource preference (y_r), and containment duration (t_i^d, t_iⁿ). The RAP then maximizes the WAM using the resource preferences (y_r), final fire size (derived from containment duration t_i^d or t_iⁿ), and fixed and deployment costs given by RDP. The overall algorithm is outlined in the next section.

WAM algorithm
[Step 0: Initialize budget level]
  TC := Budget_{LOWER_BOUND.}

[Step 1: Solve RDP] Obtain the preferred resource organization and resource deployment results (d_i^f, n_i^f, y_r, t_i^d, t_iⁿ, u_ir, u_i^r, d_ir, l_ir^w).

[Step 2: Solve RAP] Combine results from Step 1 with total cost constraint to arrive at a feasible solution for the budget point TC.

[Step 3: Solve GPO] Hot-start GPO with the feasible solution from Step 2 to obtain a globally optimal solution for the budget point TC. Hot-starting GPO with the RAP solution allows the optimizer to reach optimality more rapidly.

[Step 4: Iterate forward] TC := TC + Budget_STEP; if TC ≤ Budget_{UPPER_BOUND}, go to Step 2; else STOP.

Given this algorithm, we note that the ability to produce a globally optimal solution in Step 3 does not rely on the decomposition heuristic. Even in the absence of DCH, the GPO step could be cold-started in order to obtain an optimal solution, albeit at a much higher computational cost in terms of CPU cycles and memory. (Solving an optimization problem without providing an initial feasible solution as a starting point is referred to as a cold start.) However, DCH exploits additional mathematical structures underlying the optimization problem to produce feasible solutions quickly, so that the GPO step can be hot-started from the incumbent feasible solution to converge to a global optimal solution at only a small fraction of the original computational cost.

In order to successfully solve RDP, we analyzed the underlying model structure and data and also had discussions with fire planners and tactical fire managers. As a result, we gained two important insights. First, RDP can be further decomposed into a set of subproblems, each dealing with a single fire group. These subproblems are much more tractable in terms of size and complexity and can be solved independently. Also, since the subproblems are separable, solving each subproblem independently results in less memory requirement and improved performance.

As part of our second insight, we note that implicit consideration is given to the cost when selecting resources, even if no explicitly imposed cost constraint is considered during this first phase. This implicit consideration allows us to obtain a more globally balanced solution when the cost constraint is eventually applied in the second phase. Specifically, the following two strategies are adopted to ensure that the most cost-effective firefighting resources are selected for the proposed resource organization.

Strategy 1
Strategy 1 is most effective at low total cost levels; it is focused on procuring and deploying the most efficient resources to any given fire. Whether or not a resource is added to the proposed firefighting organization is dependent on its “efficiency,” which is calculated by considering the following factors:

• The fireline production capacity of the resource for the fire versus the costs associated with it (fixed cost, variable resource cost, or penalty cost). The fireline production capacity of a resource is the total length of fireline created around the perimeter of the fire.

• The reusability of the resource, e.g., the degree of closeness of the resource to most of the fires.

• The versatility of the resource, i.e., the degree to which it can be used productively on a large number of fires.

A composite objective function is defined in order to make the model focus on efficient resources that result in fires being contained within a reasonable time interval:

(27)

where M is chosen such that M ≥ max (TC for containing fire i).

Strategy 2
Strategy 2 is most effective at high total cost levels, where we are at liberty to pick more expensive resources, thereby accruing higher fixed costs in order to contain fires earlier. A “greedy approach” is used to deploy the best resources to each fire, with “suitability” indicating the ability to contain the fire at the earliest possible time. (Note that the greedy approach or algorithm is a heuristic-based approach used for selection of the most effective resources for each fire.) The objective function in this strategy minimizes WAB [see the objective in Equation (1)]. The single-minded focus on WAB reduction results in the best match between the fires and the resources.

Although it is a strategic planning tool, the FPA application still requires the modeling of fire growth and resource deployment characteristics at a fairly detailed level, which posed significant challenges to our modeling efforts. We analyze these challenges in the following subsections.

The computational performance of the optimizer on model instances is affected by two factors: model complexity and large model instance size. The number of rows, columns, and nonzero matrix elements is also a measure of the computational workload performed at every node of the branch-and-bound tree. As background for the more general reader, note that the set of constraints and the objective function in an optimization problem comprise a matrix. The rows of the matrix include constraints and the columns include variables. The most common algorithm used in solving an optimization problem is the branch-and-bound algorithm, which employs an iterative process to improve the quality of the solution.

The number of 0/l integer variables determines the number of nodes to be explored by the branch-and-bound algorithm in its pursuit of the global optimum. The FPA model reduces to a knapsack problem, a standard problem in combinatorial optimization, by simplifying the containment requirements so that a predetermined set of resources are assigned to contain each fire—and by removing all of the group penalties associated with resources. With this simplification, the effectiveness metric used in the objective function can be expressed in terms of resource selection decisions. Hence, the optimization problem formulated in this paper falls into the class of NP-hard problems for which the computational complexity is exponential with respect to the size of the data set representing the model instance, as was proved in Nemhauser and Wolsey [7].

The original model proposed by Rideout and Kirsch [5] required that the resource deployment and fire burn duration be measured on the discrete time scale described by seven time intervals measured in minutes (30, 60, 120, 200, 300, 450, 1,080), which denote the time elapsed since the point at which a fire ignition event is reported (t = 0). As a result, the model instances became complex because of the large number of deployment-specific 0/l variables associated with the fireline production rate and variable resource cost data for each set of deployable resources for each fire for each time interval. Such a modeling approach does not allow the interpolation of function values for points lying strictly between the discretized domain points. If a smaller number of time intervals is used to keep the number of 0/1 variables small, the quality of the solution often suffers because of a reduction of the time domain.

A way around this problem is to model the time domain as a continuous function with all time-dependent parameters (e.g., fireline produced, variable resource costs, acres, and perimeters) represented as piecewise-linear (PWL) and continuous functions of time with appropriate slopes and breakpoints. The PWL representation of data offers two distinct advantages: First, it allows for evaluation of the underlying function at all points in the domain, which improves the quality of the solution compared with the discrete time interval. Second, the PWL representation introduces no new 0/l variables because the function is convex, resulting in a compact representation of the function which contributes to the reduction of model instance size. Furthermore, from a development perspective, current state-of-the-art modeling and solver technology, such as AMPL (a modeling language for mathematical programming) [8], CBC (available from COIN-OR, which stands for COmputational INfrastructure for Operations Research), and CPLEX** (available from ILOG, Inc.), include readily available methods for modeling PWL functions using an anchor, slopes, and breakpoints of the linear segments of which the function is composed.

In analyzing initial data instances from Mississippi, Oregon, and California, we observed that some redundancies exist in input parameters such as the fire perimeter, area burned, resource line production, and variable resource cost. The line production and variable resource cost data demonstrate a PWL characteristic that is certainly over-determined by the use of discrete time intervals in the original model. Figure 1 shows plots of resource cumulative line production and variable cost (deployment cost) as a function of time. The discrete interval data in Figure 1 corresponding to seven time intervals can be represented efficiently using PWL representation. While the perimeter and area data for fires demonstrates PWL features with few breakpoints, the line production and variable resource cost data for resources is almost linear and hence can be represented by the PWL function with just one breakpoint (the breakpoint may not be common among the resources).

Figure 1

The underlying optimization model instances could be represented equivalently by a much smaller amount of data containing only the slopes and the breakpoints of the PWL functions, which would otherwise be represented redundantly by the current data, based on seven time intervals. These slopes and breakpoints can be automatically discovered computationally by building a data transformation component that extracts the slopes and breakpoints from the discrete interval data. This allows different functions (such as line production and perimeter) for different fires and resources to have different slope and breakpoint representations. This approach has the added advantage of relaxing the implicit assumption of using a common set of breakpoints along the time dimension, shared by all time-dependent data.

Fire containment and resource deployment characteristics existed that posed additional computation challenges. One such challenge is discussed in the next section.

Water tenders are special resources that do not contribute to line production but support certain specific resources (such as fire engines) by providing them with onsite retardant replenishment capability. Also, since the water tenders are available at multiple dispatch locations with unique cost and capacity constraints, we use a binary variable to represent the assignment of a water tender to an engine fighting a specific fire. This results in m × n integer variables for each combination of engines and water tenders (m engines, n water tenders). Modeling this requirement resulted in a significant decrease in the tractability of the model. In order to incorporate this business requirement for detailed modeling of the fireline production capability of the water tender resource, we proposed an innovative approximation algorithm that would require only m additional integer variables corresponding to m engines. Our approximation introduces a continuous variable l_ir^w corresponding to the additional line-production capacity of an engine resource in the presence of a water tender resource w on a fire i. By studying historical data and also by consulting FPA subject matter experts, we developed the average line production support rate for a water tender resource. Using this number, we were able to apply constraints on the value of l_ir^w to effectively model the additional line production capacity of the resource. For details of the approximation we used, please refer to the constraint equations (12) and (13).

We tested the heuristic approach on data instances from seven FPUs—Mississippi (MS), Alaska (AK), southern California (SC), Washington (WA), Wyoming (WY), Colorado (CO), and Arizona (AZ). Depending on the analysis type selected by the user, a corresponding unique set of data instances is generated for the FPU. For each FPU, three types of analysis exist: 1) a user-selected scenario (US), 2) an unconstrained or all potential scenario (UC), and 3) a combination of the user-selected scenario and the unconstrained scenario (US+UC).

A US scenario generates data corresponding to the current organization of the FPU. This scenario is a good starting point for the user in order to assess the efficiency of the current resource organization in fighting fires. A UC scenario generates all possible sets of resources that can be deployed to each dispatch location in order to generate a larger collection of deployable resources. In addition to US and UC, each FPU contributes one additional scenario data instance known as US+UC. A US+UC scenario contains both user-selected (i.e., existing) and unconstrained (i.e., all possible) resources, with each US resource explicitly marked as “must use” or “can use.” Must-use resources are those resources that form part of the optimal resource organization regardless of their productivity or efficiency; these are generally resources that have already been paid for. Can-use resources, on the other hand, are subject to the discretion of the optimization model. Table 1 shows the numbers of fires, resources, and sizes of model instances for all three scenarios for Mississippi and Alaska FPUs. The contrast between the two FPUs becomes obvious when the corresponding data elements are compared. The Mississippi FPU has fewer fires than the Alaska FPU (about 119 compared with 480); hence, the resource requirement for Mississippi is much smaller than that for Alaska. As a result, the model instance size for Mississippi is smaller than the instance size for Alaska. We obtained encouraging results, with the DCH phase consistently producing near-optimal feasible solutions for each of the instances using a fraction of the available computational resources. We also observed some interesting patterns when analyzing and comparing the US, UC, and US+UC results (Figure 2). For Mississippi FPU datasets, the value for the WAM is of the order of UC > US+UC > US. Mississippi has a maximum resource capacity of 29, of which 11 are must-use resources; in other words, 11 specific resources must be procured regardless of their efficiency or effectiveness. This leaves the optimizer with only 18 resources to choose from the pool of resources. These 11 resources cost about $2.6M; hence, we see that the Mississippi WAM curve for US+UC follows the US curve very closely until $6M, after which the WAM for US+UC improves substantially over US. This observation results from the fact that, at lower budget levels, the fixed costs incurred by must-use resources bias the budget allocation and prevent US+UC from achieving significantly higher WAM than the corresponding US scenario. It also explains why the UC scenario has a much higher WAM than US or US+UC, since the former is not constrained by must-use resources and may pick the most cost-effective candidates from the pool of resources.

Figure 2

Another interesting observation we can make when examining the results is that as the budget level increases, the number of fires contained at the incremental budget level decreases in some cases. In the Alaska UC data instance (row 3 of Table 2), the number of fires that escaped at a cost of $18M and $19M actually increases from 243 to 267, but the WAM increases by 76K acres. Upon further study of the results, we observe that adding $1M to the budget enables the optimizer to procure more efficient resources, thereby containing higher-intensity fires. Recall that the objective function in the model maximizes WAM; therefore, it is understandable that the model must allow some low-intensity fires to escape in exchange for fire-suppression dollars that can be spent otherwise to achieve higher WAM.

The purpose of this validation exercise was to analyze the impact of some of the key assumptions used in developing the FPA model. Specifically, we relax the assumption about having perfect knowledge of fire occurrences and evaluate the sensitivity of the solution to multiple fire occurrence scenarios. We also assess the effect of resource redeployment among simultaneous fires on the containment results.

The FPA model is deterministic and runs on a representative fire season scenario generated from historical data. Uncertainty exists with respect to the fire season, the number of fires, time of ignition, and location and growth of fires. Additional micro-parameters exist that may alter the workload profile associated with the realized fire season scenario. (The term micro-parameters refers to additional fire characteristics and stochasticity of the underlying data.) Uncertainty in the fire data invalidates the optimality of the incumbent budgeting and associated resource allocation decisions from the FPA model. Therefore, we undertook a model validation exercise to assess the gap between the results of expected acreage burned from a multiple-scenario version of the optimization model and the same obtained from running the deterministic model on a single scenario.

We defined the comprehensive multiple-scenario budgeting problem as the recourse problem (RP). The current approach is defined as the expected mean-value problem (EEV), and the optimistic lower-bounding as the wait-and-see problem (WS) [9]:

(28)

(29)

(30)

(31)

(32)

In our attempt to characterize the gaps that result from the process of overlooking uncertainty, we computed the values of theoretical measures such as the expected value of perfect information (EVPI) and the value of the stochastic solution (VSS) by repeatedly utilizing the deterministic optimization model.

Figure 3 depicts the results of the testing performed on California and Alaska data instances. Each plot contains the WAB obtained for different budget points for the constrained and unconstrained scenarios. In analyzing the results, we observed that WAB[unconstrained scenario] is less than WAB[constrained scenario]. We also observed that the difference between WAB[unconstrained scenario] and WAB[constrained scenario] is not monotonic across all scenarios.

Figure 3

We concluded that resource organization is critical in scenarios having large and/or simultaneous fires. Also, having resources with short response time (i.e., having an early arrival) and high line production capability helps in reducing the containment duration, which in turn reduces the WAB. For scenarios having small fires (i.e., fires with low growth rate or small escape size), resource selection is less critical. Finally, we also concluded that having access to more resources helps us to attack simultaneous fires more effectively, since the optimization model does not allow redeployment of resources to multiple fires in the group.

Another important assumption is that resources cannot be shared (redeployed) among simultaneous fires in the same fire group. In other words, the FPA model assumes that simultaneous fires start at exactly the same time, and hence it does not permit the use of a resource on more than one fire. This assumption reduces the availability of resources to other fires and is counter to the policies used in the field to allocate resources. The assumption is based upon the fact that the optimizer is a strategic planning tool for determining preparedness budgets and not an optimal resource deployment tool. Nonetheless, we are interested in analyzing the impact of this assumption on the optimal solution.

In performing the model validation, we followed a process illustrated in Figure 4. We used a simulation model that could generate a fire scenario and used a predefined dispatch policy to contain the fires. The simulation model also had the capability to redeploy resources to simultaneous fires. The scenario generated by the simulation model was then communicated to the optimization engine, and the results of the simulation engine were compared with those from the optimization engine to assess the impact of redeployment of resources on simultaneous fires. The simulation model we chose was the California Fire Economics Simulator Version 2 (CFES2), a tool for stochastic simulation analysis of the initial response system. CFES2 takes into account resource reuse through an internal dispatch policy that can deploy resources to one fire early in the day and then redeploy them to other fires later in the day [10].

Figure 4

To make a sensible comparison, we designed the following experiment:

1. Configure CFES2 in such a way that it generates a scenario comprising a large number of simultaneous fire occurrences.

2. Run the scenario in CFES2 and collect results with respect to the number of fires that are contained, as well as containment durations, fire perimeters, acres burned, resources deployed, and firelines constructed.

3. Transform the CFES2 scenario input into the optimizer input format while ensuring that the optimizer accesses the same data as the simulator, including fire occurrences, fire growth behaviors, available resources, resource fireline productivity, and so on.

4. Run the optimizer with the transformed scenario data and collect the results.

5. Repeat steps 1–4 for several different scenarios.

We use the experiment to estimate the conditional probability q of the optimizer allowing a fire to escape when the same fire is contained with the larger set of resources in the simulator, i.e., q = P(escaped_FPA| contained_CFES). If the value of q approaches 1, the impact of reuse is significant and should not be ignored; if the value of q approaches 0, the impact is minimal, and there is no need to change the current assumption. We ran the experiment with nine different scenarios, and Table 3 shows the outcomes.

From Table 3, one can estimate as

Here, denotes the expected or average value for the probability of the optimizer allowing a fire to escape when the same fire is contained using the larger set of resources in the simulator; denotes the condition probability value from each scenario.

A value of  ≥ 0.5 explains the large deviations in the WAB given by the optimizer and simulator. Hence, we concluded that resource reuse is a crucial factor that should not be neglected.

We have developed a robust strategic budgeting model for managing the initial response for wildfires by strengthening the model formulation of Rideout and Kirsch [5] and then enhancing it so that it supports interdependent resources such as air tankers and water tenders. The model has been implemented within the FPA PM prototype system. The richness of the model makes it suitable for use in modeling initial response activities in other natural disaster management areas such as hurricanes, floods, and contagious diseases.

On the basis of our analysis of the field data from a set of FPUs, we further reduced the size of the formulation through automatic PWL representation of certain input parameter data such as line production, perimeter growth, and hourly cost. We developed a flexible PWL function-generator method that is capable of generating a hierarchy of model instances of different levels of computational complexity for different levels of data approximation. Even for the most accurate (i.e., least approximate) PWL data representation, we obtain a sixfold data reduction in the number of columns of the matrix for the optimization model instance, and an eightfold reduction in the number of 0/1 variables for the Oregon and Mississippi instances. Similar reductions were observed for other instances as well.

To solve the resulting model, we developed a scalable heuristic DCH that forms the basis of the DCH–GPO optimization approach that is amenable to multiple-scenario (stochastic programming) versions of the model. The DCH–GPO–S solution method consistently ran to completion without exceeding the available computational resource limitations (2 GB RAM, two hours of CPU time) and resulted in a performance improvement of a factor of more than 150 with respect to the GPO method on representative problem instances. The speedup factors were even more impressive for the real datasets from the seven FPUs.

In preparedness budgeting for wildfire management, strategic decisions correspond to the determination of which fire management resources to maintain for the year, and tactical decisions correspond to how best to deploy these resources. The strategic decisions must be made before fires break out, and the tactical decisions take place after these breakouts.

We plan to investigate the potential advantages of applying the two-stage stochastic programming approach in order to develop preparedness budgets for managing wildland fires. (The term stochastic programming refers to optimization problems for which part of the input is a probability distribution that describes the likelihood of each underlying scenario.) Stochastic programming is especially suited for optimization in a setting with distinctly different decisions, in which the strategic decisions are made on the basis of uncertain information, and the tactical decisions are made after learning the outcome of the events that were uncertain at the time the strategic decisions were made. For further details on stochastic programming, see [9].

The strategic planning model developed in this paper currently uses a single representative wildfire profile or scenario. This scenario is likely to be different from the actual wildfire scenarios. Two-stage stochastic programming provides an appropriate and tractable framework for obtaining more robust solutions by simultaneously considering several scenarios. Preliminary scenario-generation work is currently underway to advance this line of investigation.

We are also considering a different paradigm of modeling the strategic budgeting problem with the simplified but rather pragmatic assumption that one need consider only a finite collection of initial response resource organizations and evaluate each such organization for its effectiveness using appropriate modeling of stochastic resource arrival and fire ignition, size, and containment patterns. Once the cost and effectiveness of each potential organization is computed using a detailed stochastic modeling and analysis, a simple high-level optimization can weigh the relative benefits of each potential organization against its costs in order to find an optimal initial resource organization.

We are also exploring the application of modeling and solution approaches developed herein to other areas of disaster management such as flood management and disease control, for which better preparedness and effective initial response are two key planning areas for government agencies. These natural disasters, like wildfires, require strategic national-level preparedness planning that must be undertaken despite uncertainty regarding the level of hazards and the number of events that will require a quick response.

This work was supported by the Forest Service of the U.S. Department of Agriculture under Contract No. 43-82X9-3-5073. We also thank Pranav Gupta and Jeremy Fried for their contributions and valuable input toward validating the optimization model using CFES2.

*Trademark, service mark, or registered trademark of International Business Machines Corporation in the United States, other countries, or both.
**Trademark, service mark, or registered trademark of ILOG, Inc. or Intel Corporation in the United States, other countries, or both.

Received September 22, 2006; accepted for publication October 19, 2006; Published online May 22, 2007.