View source: R/add_heuristic_solver.R
add_heuristic_solver  R Documentation 
Specify that solutions should be generated using a backwards stepwise
heuristic algorithm (inspired by Cabeza et al. 2004,
Korte & Vygen 2000, Probert et al. 2016). Ideally,
solutions should be generated using exact algorithm solvers (e.g.
add_rsymphony_solver()
or add_gurobi_solver()
)
because they are guaranteed to identify optimal solutions (Rodrigues & Gaston
2002).
add_heuristic_solver( x, number_solutions = 1, initial_sweep = TRUE, verbose = TRUE )
x 
ProjectProblem object. 
number_solutions 

initial_sweep 

verbose 

The heuristic algorithm used to generate solutions is described below. It is heavily inspired by the costsharing backwards heuristic algorithm conventionally used to guide the prioritization of species recovery projects (Probert et al. 2016).
All actions and projects are initially selected for funding.
A set of rules are then used to deselect actions and projects based on locked constraints (if any). Specifically, (i) actions which are which are locked out are deselected, and (ii) projects which are associated with actions that are locked out are also deselected.
If the argument to initial_sweep
is TRUE
, then a set of
rules are then used to deselect actions and projects
based on budgetary constraints (if present). Specifically, (i) actions
which exceed the budget are deselected, (ii) projects which are
associated with a set of actions that exceed the budget are deselected,
and (iii) actions which are not associated with any project (excepting
locked in actions) are also deselected.
If the objective function is to maximize biodiversity subject
to budgetary constraints (e.g. add_max_richness_objective()
)
then go to step 5. Otherwise, if the objective is to minimize cost
subject to biodiversity constraints (i.e.
add_min_set_objective()
) then go to step 7.
The next step is repeated until (i) the number of desired solutions is obtained, and (ii) the total cost of the remaining actions that are selected for funding is within the budget. After both of these conditions are met, the algorithm is terminated.
Each of the remaining projects that are currently selected for funding are evaluated according to how much the performance of the solution decreases when the project is deselected for funding, relative to the cost of the project not shared by other remaining projects. This can be expressed mathematically as:
B_j = (V(J)  V(J  j)) / C_j
Where J is the set of remaining projects currently selected for funding (indexed by j), B_j is the benefit associated with funding project j, V(J) is the objective value associated with the solution where all remaining projects are funded, V(J  j) is the objective value associated with the solution where all remaining projects except for project j are funded, and C_j is the sum cost of all of the actions associated with project j—excluding locked in actions—with the cost of each action divided by the total number of remaining projects that share the action (e.g. if two projects both share a $100 action, then this action contributes $50 to the overall cost of each project).
The project with the smallest benefit (i.e. B_j value) is then deselected for funding. In cases where multiple projects have the same benefit (B_j) value, the project with the greatest overall cost (including actions which are shared among multiple remaining projects) is deselected.
The next step is repeated until (i) the number of desired solutions is obtained or (ii) no action can be deselected for funding without the probability of any feature expecting to persist falling below its target probability of persistence. After one or both of these conditions are met, the algorithm is terminated.
Each of the remaining projects that are currently selected for funding are evaluated according to how much the performance of the solution decreases when the project is deselected for funding, relative to the cost of the project not shared by other remaining projects. This can be expressed mathematically as:
B_j = ((sum_f^F P_f(J)  T_f)  (sum_f^F P_f(J  j)  T_f)) / C_j
Where F is the set of features (indexed by f), T_f is the target for feature f, P is the set of remaining projects that are selected for funding (indexed by j), C_j is the cost of all of the actions associated with project j—excluding locked in actions—and accounting for shared costs among remaining projects (e.g. if two projects both share a $100 action, then this action contributes $50 to the overall cost of each project), B_p is the benefit associated with funding project p, P(J) is probability that each feature is expected to persist when the remaining projects (J) are funded, and P(J  j) is the probability that each feature is expected to persist when all the remaining projects except for action j are funded.
The project with the smallest benefit (i.e. B_j value) is then deselected for funding. In cases where multiple projects have the same B_j value, the project with the greatest overall cost (including actions which are shared among multiple remaining projects) is deselected.
ProjectProblem object with the solver added to it.
Rodrigues AS & Gaston KJ (2002) Optimisation in reserve selection procedures—why not? Biological Conservation, 107, 123–129.
Cabeza M, Araujo MB, Wilson RJ, Thomas CD, Cowley MJ & Moilanen A (2004) Combining probabilities of occurrence with spatial reserve design. Journal of Applied Ecology, 41, 252–262.
Korte B & Vygen J (2000) Combinatorial Optimization. Theory and Algorithms. SpringerVerlag, Berlin, Germany.
Probert W, Maloney RF, Mellish B, and Joseph L (2016) Project Prioritisation Protocol (PPP). Formerly available at https://github.com/probot (copy available at https://github.com/jeffreyhanson/ppp).
solvers.
# load ggplot2 package for making plots library(ggplot2) # load data data(sim_projects, sim_features, sim_actions) # build problem with heuristic solver and $200 p1 < problem(sim_projects, sim_actions, sim_features, "name", "success", "name", "cost", "name") %>% add_max_richness_objective(budget = 200) %>% add_binary_decisions() %>% add_heuristic_solver() # print problem print(p1) ## Not run: # solve problem s1 < solve(p1) # print solution print(s1) # plot solution plot(p1, s1) ## End(Not run)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.