Add neighbor constraints

Add constraints to a conservation planning problem to ensure that all selected planning units in the solution have at least a certain number of neighbors that are also selected in the solution.

# S4 method for ConservationProblem,ANY,ANY,ANY
add_neighbor_constraints(x, k, zones, data)

# S4 method for ConservationProblem,ANY,ANY,data.frame
add_neighbor_constraints(x, k, zones, data)

# S4 method for ConservationProblem,ANY,ANY,matrix
add_neighbor_constraints(x, k, zones, data)

# S4 method for ConservationProblem,ANY,ANY,array
add_neighbor_constraints(x, k, zones, data)

Arguments

x	ConservationProblem-class object.
k	integer minimum number of neighbors for selected planning units in the solution. For problems with multiple zones, the argument to k must have an element for each zone.
zones	matrix or Matrix object describing the neighborhood scheme for different zones. Each row and column corresponds to a different zone in the argument to x, and cell values must contain binary numeric values (i.e. one or zero) that indicate if neighboring planning units (as specified in the argument to data) should be considered neighbors if they are allocated to different zones. The cell values along the diagonal of the matrix indicate if planning units that are allocated to the same zone should be considered neighbors or not. The default argument to zones is an identity matrix (i.e. a matrix with ones along the matrix diagonal and zeros elsewhere), so that planning units are only considered neighbors if they are both allocated to the same zone.
data	NULL, matrix, Matrix, data.frame, or array object showing which planning units are neighbors with each other. The argument defaults to NULL which means that the neighborhood data is calculated automatically using the connected_matrix function. See the Details section for more information.

Value

ConservationProblem-class object with the constraint added to it.

Details

This function uses neighborhood data identify solutions that surround planning units with a minimum number of neighbors. It was inspired by the mathematical formulations detailed in Billionnet (2013) and Beyer et al. (2016).

The argument to data can be specified in several ways:

NULL

neighborhood data should be calculated automatically using the connected_matrix function. This is the default argument. Note that the neighborhood data must be manually defined using one of the other formats below when the planning unit data in the argument to x is not spatially referenced (e.g. in data.frame or numeric format).

matrix, Matrix

where rows and columns represent different planning units and the value of each cell indicates if the two planning units are neighbors or not. Cell values should be binary numeric values (i.e. one or zero). Cells that occur along the matrix diagonal have no effect on the solution at all because each planning unit cannot be a neighbor with itself.

data.frame

containing the fields (columns) "id1", "id2", and "boundary". Here, each row denotes the connectivity between two planning units following the Marxan format. The field boundary should contain binary numeric values that indicate if the two planning units specified in the fields "id1" and "id2" are neighbors or not. This data can be used to describe symmetric or asymmetric relationships between planning units. By default, input data is assumed to be symmetric unless asymmetric data is also included (e.g. if data is present for planning units 2 and 3, then the same amount of connectivity is expected for planning units 3 and 2, unless connectivity data is also provided for planning units 3 and 2). If the argument to x contains multiple zones, then the columns "zone1" and "zone2" can optionally be provided to manually specify if the neighborhood data pertain to specific zones. The fields "zone1" and "zone2" should contain the character names of the zones. If the columns "zone1" and "zone2" are present, then the argument to zones must be NULL.

array

containing four-dimensions where binary numeric values indicate if planning unit should be treated as being neighbors with every other planning unit when they are allocated to every combination of management zone. The first two dimensions (i.e. rows and columns) correspond to the planning units, and second two dimensions correspond to the management zones. For example, if the argument to data had a value of 1 at the index data[1, 2, 3, 4] this would indicate that planning unit 1 and planning unit 2 should be treated as neighbors when they are allocated to zones 3 and 4 respectively.

References

Beyer HL, Dujardin Y, Watts ME, and Possingham HP (2016) Solving conservation planning problems with integer linear programming. Ecological Modelling, 228: 14--22.

Billionnet A (2013) Mathematical optimization ideas for biodiversity conservation. European Journal of Operational Research, 231: 514--534.

See also

constraints, penalties.

Examples

# load data
data(sim_pu_raster, sim_features, sim_pu_zones_stack, sim_features_zones)

# create minimal problem
p1 <- problem(sim_pu_raster, sim_features) %>%
      add_min_set_objective() %>%
      add_relative_targets(0.1)

# create problem with constraints that require 1 neighbor
# and neighbors are defined using a rook-style neighborhood
p2 <- p1 %>% add_neighbor_constraints(1)

# create problem with constraints that require 2 neighbor
# and neighbors are defined using a rook-style neighborhood
p3 <- p1 %>% add_neighbor_constraints(2)

# create problem with constraints that require 3 neighbor
# and neighbors are defined using a queen-style neighborhood
p4 <- p1 %>% add_neighbor_constraints(3,
               data = connected_matrix(sim_pu_raster, directions = 8))
# solve problems
s1 <- stack(list(solve(p1), solve(p2), solve(p3), solve(p4)))
#> Optimize a model with 5 rows, 90 columns and 450 nonzeros
#> Variable types: 0 continuous, 90 integer (90 binary)
#> Coefficient statistics:
#>   Matrix range     [2e-01, 9e-01]
#>   Objective range  [2e+02, 2e+02]
#>   Bounds range     [1e+00, 1e+00]
#>   RHS range        [3e+00, 8e+00]
#> Found heuristic solution: objective 2337.9617505
#> Presolve time: 0.00s
#> Presolved: 5 rows, 90 columns, 450 nonzeros
#> Variable types: 0 continuous, 90 integer (90 binary)
#> Presolved: 5 rows, 90 columns, 450 nonzeros
#> 
#> 
#> Root relaxation: objective 1.931582e+03, 12 iterations, 0.00 seconds
#> 
#>     Nodes    |    Current Node    |     Objective Bounds      |     Work
#>  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
#> 
#>      0     0 1931.58191    0    4 2337.96175 1931.58191  17.4%     -    0s
#> H    0     0                    1985.6818841 1931.58191  2.72%     -    0s
#> 
#> Explored 1 nodes (12 simplex iterations) in 0.00 seconds
#> Thread count was 1 (of 4 available processors)
#> 
#> Solution count 2: 1985.68 2337.96 
#> 
#> Optimal solution found (tolerance 1.00e-01)
#> Best objective 1.985681884076e+03, best bound 1.931581908865e+03, gap 2.7245%
#> Optimize a model with 95 rows, 90 columns and 828 nonzeros
#> Variable types: 0 continuous, 90 integer (90 binary)
#> Coefficient statistics:
#>   Matrix range     [2e-01, 1e+00]
#>   Objective range  [2e+02, 2e+02]
#>   Bounds range     [1e+00, 1e+00]
#>   RHS range        [3e+00, 8e+00]
#> Found heuristic solution: objective 2183.0924422
#> Presolve time: 0.00s
#> Presolved: 95 rows, 90 columns, 828 nonzeros
#> Variable types: 0 continuous, 90 integer (90 binary)
#> Presolved: 95 rows, 90 columns, 828 nonzeros
#> 
#> 
#> Root relaxation: objective 1.932118e+03, 25 iterations, 0.00 seconds
#> 
#>     Nodes    |    Current Node    |     Objective Bounds      |     Work
#>  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
#> 
#>      0     0 1932.11830    0    6 2183.09244 1932.11830  11.5%     -    0s
#> H    0     0                    1993.6247371 1932.11830  3.09%     -    0s
#> 
#> Explored 1 nodes (25 simplex iterations) in 0.00 seconds
#> Thread count was 1 (of 4 available processors)
#> 
#> Solution count 2: 1993.62 2183.09 
#> 
#> Optimal solution found (tolerance 1.00e-01)
#> Best objective 1.993624737145e+03, best bound 1.932118304023e+03, gap 3.0852%
#> Optimize a model with 95 rows, 90 columns and 828 nonzeros
#> Variable types: 0 continuous, 90 integer (90 binary)
#> Coefficient statistics:
#>   Matrix range     [2e-01, 2e+00]
#>   Objective range  [2e+02, 2e+02]
#>   Bounds range     [1e+00, 1e+00]
#>   RHS range        [3e+00, 8e+00]
#> Found heuristic solution: objective 3605.4363089
#> Presolve removed 2 rows and 4 columns
#> Presolve time: 0.00s
#> Presolved: 93 rows, 86 columns, 798 nonzeros
#> Variable types: 0 continuous, 86 integer (86 binary)
#> Presolved: 93 rows, 86 columns, 798 nonzeros
#> 
#> 
#> Root relaxation: objective 1.939110e+03, 50 iterations, 0.00 seconds
#> 
#>     Nodes    |    Current Node    |     Objective Bounds      |     Work
#>  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
#> 
#>      0     0 1939.10993    0   14 3605.43631 1939.10993  46.2%     -    0s
#> H    0     0                    2416.7011836 1939.10993  19.8%     -    0s
#>      0     0 1941.28796    0   16 2416.70118 1941.28796  19.7%     -    0s
#> H    0     0                    2019.4822081 1941.28796  3.87%     -    0s
#> 
#> Cutting planes:
#>   Cover: 7
#>   MIR: 2
#> 
#> Explored 1 nodes (69 simplex iterations) in 0.01 seconds
#> Thread count was 1 (of 4 available processors)
#> 
#> Solution count 3: 2019.48 2416.7 3605.44 
#> 
#> Optimal solution found (tolerance 1.00e-01)
#> Best objective 2.019482208068e+03, best bound 1.941287964291e+03, gap 3.8720%
#> Optimize a model with 95 rows, 90 columns and 1084 nonzeros
#> Variable types: 0 continuous, 90 integer (90 binary)
#> Coefficient statistics:
#>   Matrix range     [2e-01, 3e+00]
#>   Objective range  [2e+02, 2e+02]
#>   Bounds range     [1e+00, 1e+00]
#>   RHS range        [3e+00, 8e+00]
#> Found heuristic solution: objective 2746.9251892
#> Presolve removed 1 rows and 1 columns
#> Presolve time: 0.00s
#> Presolved: 94 rows, 89 columns, 1074 nonzeros
#> Variable types: 0 continuous, 89 integer (89 binary)
#> Presolved: 94 rows, 89 columns, 1074 nonzeros
#> 
#> 
#> Root relaxation: objective 1.933734e+03, 46 iterations, 0.00 seconds
#> 
#>     Nodes    |    Current Node    |     Objective Bounds      |     Work
#>  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
#> 
#>      0     0 1933.73436    0   12 2746.92519 1933.73436  29.6%     -    0s
#> H    0     0                    2416.4661768 1933.73436  20.0%     -    0s
#>      0     0 1938.57643    0   15 2416.46618 1938.57643  19.8%     -    0s
#> H    0     0                    2018.7760790 1938.57643  3.97%     -    0s
#> 
#> Cutting planes:
#>   Cover: 5
#>   MIR: 6
#> 
#> Explored 1 nodes (59 simplex iterations) in 0.01 seconds
#> Thread count was 1 (of 4 available processors)
#> 
#> Solution count 3: 2018.78 2416.47 2746.93 
#> 
#> Optimal solution found (tolerance 1.00e-01)
#> Best objective 2.018776078984e+03, best bound 1.938576429999e+03, gap 3.9727%

# plot solutions
plot(s1, box = FALSE, axes = FALSE,
     main = c("basic solution", "1 neighbor", "2 neighbors", "3 neighbors"))
# create minimal problem with multiple zones
p5 <- problem(sim_pu_zones_stack, sim_features_zones) %>%
      add_min_set_objective() %>%
      add_relative_targets(matrix(0.1, ncol = 3, nrow = 5))

# create problem where selected planning units require at least 2 neighbors
# for each zone and planning units are only considered neighbors if they
# are allocated to the same zone
z6 <- diag(3)
print(z6)
#>      [,1] [,2] [,3]
#> [1,]    1    0    0
#> [2,]    0    1    0
#> [3,]    0    0    1
p6 <- p5 %>% add_neighbor_constraints(rep(2, 3), z6)

# create problem where the planning units in zone 1 don't explicitly require
# any neighbors, planning units in zone 2 require at least 1 neighbors, and
# planning units in zone 3 require at least 2 neighbors. As before, planning
# units are still only considered neighbors if they are allocated to the
# same zone
p7 <- p5 %>% add_neighbor_constraints(c(0, 1, 2), z6)

# create problem given the same constraints as outlined above, except
# that when determining which selected planning units are neighbors,
# planning units that are allocated to zone 1 and zone 2 can also treated
# as being neighbors with each other
z8 <- diag(3)
z8[1, 2] <- 1
z8[2, 1] <- 1
print(z8)
#>      [,1] [,2] [,3]
#> [1,]    1    1    0
#> [2,]    1    1    0
#> [3,]    0    0    1
p8 <- p5 %>% add_neighbor_constraints(c(0, 1, 2), z8)
# solve problems
s2 <- list(p5, p6, p7, p8)
s2 <- lapply(s2, solve)
#> Optimize a model with 105 rows, 270 columns and 1620 nonzeros
#> Variable types: 0 continuous, 270 integer (270 binary)
#> Coefficient statistics:
#>   Matrix range     [2e-01, 1e+00]
#>   Objective range  [2e+02, 2e+02]
#>   Bounds range     [1e+00, 1e+00]
#>   RHS range        [1e+00, 8e+00]
#> Found heuristic solution: objective 7019.1222763
#> Presolve time: 0.01s
#> Presolved: 105 rows, 270 columns, 1620 nonzeros
#> Variable types: 0 continuous, 270 integer (270 binary)
#> Presolved: 105 rows, 270 columns, 1620 nonzeros
#> 
#> 
#> Root relaxation: objective 5.935429e+03, 100 iterations, 0.00 seconds
#> 
#>     Nodes    |    Current Node    |     Objective Bounds      |     Work
#>  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
#> 
#>      0     0 5935.42867    0   13 7019.12228 5935.42867  15.4%     -    0s
#> H    0     0                    6082.2792264 5935.42867  2.41%     -    0s
#> 
#> Explored 1 nodes (100 simplex iterations) in 0.01 seconds
#> Thread count was 1 (of 4 available processors)
#> 
#> Solution count 2: 6082.28 7019.12 
#> 
#> Optimal solution found (tolerance 1.00e-01)
#> Best objective 6.082279226435e+03, best bound 5.935428674960e+03, gap 2.4144%
#> Optimize a model with 375 rows, 270 columns and 2760 nonzeros
#> Variable types: 0 continuous, 270 integer (270 binary)
#> Coefficient statistics:
#>   Matrix range     [2e-01, 2e+00]
#>   Objective range  [2e+02, 2e+02]
#>   Bounds range     [1e+00, 1e+00]
#>   RHS range        [1e+00, 8e+00]
#> Found heuristic solution: objective 10188.214728
#> Presolve removed 6 rows and 9 columns
#> Presolve time: 0.01s
#> Presolved: 369 rows, 261 columns, 2685 nonzeros
#> Variable types: 0 continuous, 261 integer (261 binary)
#> Presolved: 369 rows, 261 columns, 2685 nonzeros
#> 
#> 
#> Root relaxation: objective 5.950461e+03, 264 iterations, 0.01 seconds
#> 
#>     Nodes    |    Current Node    |     Objective Bounds      |     Work
#>  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
#> 
#>      0     0 5950.46090    0   51 10188.2147 5950.46090  41.6%     -    0s
#> H    0     0                    7453.2524990 5950.46090  20.2%     -    0s
#> H    0     0                    6495.8274057 5950.46090  8.40%     -    0s
#> 
#> Explored 1 nodes (264 simplex iterations) in 0.02 seconds
#> Thread count was 1 (of 4 available processors)
#> 
#> Solution count 3: 6495.83 7453.25 10188.2 
#> 
#> Optimal solution found (tolerance 1.00e-01)
#> Best objective 6.495827405667e+03, best bound 5.950460895938e+03, gap 8.3956%
#> Optimize a model with 375 rows, 270 columns and 2670 nonzeros
#> Variable types: 0 continuous, 270 integer (270 binary)
#> Coefficient statistics:
#>   Matrix range     [2e-01, 2e+00]
#>   Objective range  [2e+02, 2e+02]
#>   Bounds range     [1e+00, 1e+00]
#>   RHS range        [1e+00, 8e+00]
#> Found heuristic solution: objective 7339.4976993
#> Presolve removed 91 rows and 3 columns
#> Presolve time: 0.01s
#> Presolved: 284 rows, 267 columns, 2357 nonzeros
#> Variable types: 0 continuous, 267 integer (267 binary)
#> Presolved: 284 rows, 267 columns, 2357 nonzeros
#> 
#> 
#> Root relaxation: objective 5.941652e+03, 197 iterations, 0.00 seconds
#> 
#>     Nodes    |    Current Node    |     Objective Bounds      |     Work
#>  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
#> 
#>      0     0 5941.65239    0   25 7339.49770 5941.65239  19.0%     -    0s
#> H    0     0                    6738.7445245 5941.65239  11.8%     -    0s
#> H    0     0                    6326.6355905 5941.65239  6.09%     -    0s
#> 
#> Explored 1 nodes (197 simplex iterations) in 0.01 seconds
#> Thread count was 1 (of 4 available processors)
#> 
#> Solution count 3: 6326.64 6738.74 7339.5 
#> 
#> Optimal solution found (tolerance 1.00e-01)
#> Best objective 6.326635590527e+03, best bound 5.941652389062e+03, gap 6.0851%
#> Optimize a model with 375 rows, 270 columns and 3250 nonzeros
#> Variable types: 0 continuous, 270 integer (270 binary)
#> Coefficient statistics:
#>   Matrix range     [2e-01, 2e+00]
#>   Objective range  [2e+02, 2e+02]
#>   Bounds range     [1e+00, 1e+00]
#>   RHS range        [1e+00, 8e+00]
#> Found heuristic solution: objective 7926.6786941
#> Presolve removed 91 rows and 3 columns
#> Presolve time: 0.01s
#> Presolved: 284 rows, 267 columns, 2647 nonzeros
#> Variable types: 0 continuous, 267 integer (267 binary)
#> Presolved: 284 rows, 267 columns, 2647 nonzeros
#> 
#> 
#> Root relaxation: objective 5.941652e+03, 178 iterations, 0.00 seconds
#> 
#>     Nodes    |    Current Node    |     Objective Bounds      |     Work
#>  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
#> 
#>      0     0 5941.65239    0   25 7926.67869 5941.65239  25.0%     -    0s
#> H    0     0                    6740.4618068 5941.65239  11.9%     -    0s
#> H    0     0                    6327.3313218 5941.65239  6.10%     -    0s
#> 
#> Explored 1 nodes (178 simplex iterations) in 0.02 seconds
#> Thread count was 1 (of 4 available processors)
#> 
#> Solution count 3: 6327.33 6740.46 7926.68 
#> 
#> Optimal solution found (tolerance 1.00e-01)
#> Best objective 6.327331321838e+03, best bound 5.941652389062e+03, gap 6.0954%
s2 <- lapply(s2, category_layer)
s2 <- stack(s2)
names(s2) <- c("basic problem", "p6", "p7", "p8")

# plot solutions
plot(s2, main = names(s2), box = FALSE, axes = FALSE)