Transcript ppt
Integer Programming and Spatial
Landscape Planning
(an example from reserve design)
Lecture 15 (6/1/2015)
Spatial Optimization to Aid Reserve
Design
• Constructing reserve networks with spatial
structures that are conducive to the health
and integrity of the ecosystem that we
wish to preserve
Spatial Attributes
•
•
•
•
•
Size
Connectivity
Perimeter-area ratio
Proximity
Contiguity
Protecting Grassland Birds in Illinois
The Henslow's Sparrow
Photo by Merilee Janusz
Upland Sandpiper
Photo by Dave Spleha
http://www.kaneforest.com/
Eastern Meadowlark
Photo by Gene Oleynik
Protecting Grassland
Birds in Illinois
Which parcels should
be selected for
purchase to maximize
the total area protected
without exceeding the
budget?
Budget = B;
Purchase price of parcel i is ci;
Area of parcel i is ai
Budget = B;
Purchase price of parcel i is ci;
Area of parcel i is ai
Mathematical model formulation:
Define the decision variables:
xi is one if parcel i is to be
purchased, and 0 otherwise
Define objective function (what
do we want?):
Max
a x
i i
i
Define constraints:
c x
A
i i
i
B
xi 0,1
0-1 mathematical program
Species Representation
Suppose you want to represent
each species at least once in your
reserve network:
Preserve species ‘a’ in at
least one location:
x1 x7 x9 1
1
c
a
2
b
3
6
c
d
4 c
e
5
b e
Preserve species ‘b’ in at
least one location:
8
12
e
x1 x5 x7 x11 1
Preserve species ‘c’, ‘d’, ‘e’
in at least one location:
x1 x2 x4 x8 x9 1
x3 x6 x10 1
x4 x5 x11 x12 1
d
7 b
a
9
a
c
10
d
11 e
b
c
Species Representation cont.
…and of course we still
have a budget and want to
maximize the total protected
area:
12
Max
a x
i i
i=1
s.t.
12
c x
i 1
i i
B
x1 x7 x9 1
x1 x5 x7 x11 1
x1 x2 x4 x8 x9 1
x3 x6 x10 1
x4 x5 x11 x12 1
xi 0,1
Species Representation cont.
• In a general form:
Max
a x
iI
i i
s.t.
c x
iI
i i
x
iS j
i
B
1
j J
xi 0,1
where: i indexes the sites, j the species. I is the complete set of sites available
for conservation purchase, J is the set of species to preserve and S j is
the set of sites that contain a population of species j.
Maximal Species Representation
• Let’s introduce a binary indicator variable y j that turns
on (takes the value of one) if species j is protected in at
least one viable population.
• We need a trigger mechanism that drives the value of y j .
• Let’s add a constraint:
x
iS j
i
yj
j J
• Our objective function will become:
Max
y
jJ
j
Maximal Species Representation
cont.
• Our mathematical program becomes:
Max
y
jJ
j
s.t.:
c x
iI
i i
x
iS j
i
B
yj
xi , y j 0,1
j J
Spatially Explicit Reserve Selection Subject
to Minimum Contiguous Habitat Size
Requirements
Threatened grassland birds in
the analysis area require at
least 100 ha of habitat in
contiguous patches
Minimum Contiguous Habitat Size
Requirements
• Step 1: Enumerate all feasible contiguous clusters of
parcels. Let C denote this potentially enormous set.
• Step 2: Enforce the logical condition that a parcel can
only be protected if it is part of at least one feasible
cluster that is protected. To enforce this condition,
introduce indicator variable y j that turns on
if cluster j is protected.
y
jPi
j
xi
i I
where Pi is the set of feasible clusters
that contain parcel i .
Minimum Contiguous Habitat Size
Requirements cont.
• Step 3: We also need to ensure that a cluster is declared
to be protected only if each parcel that comprise the
cluster is protected:
x
iC j
Cj yj
i
C j C
Here yj may turn on if all xis in Cj are on. Is that enough?
We also need to make sure that: yj must turn on if all xis
in Cj are on. Why and how can we do that?
x y
iC j
i
j
C j 1
C j C
Minimum Contiguous Habitat Size
Requirements cont.
Max ai xi
i
subject to :
A parcel can only be protected if
it is part of at least one feasible
cluster that is protected
A cluster may be protected if
each parcel that makes up the
cluster is protected
c x
i i
B
Budget
i
y
j
xi
i I
i
Cj yj
Cj C
jPi
x
iC j
x y
A cluster must be protected if
each parcel that makes up the
cluster is protected
Protected area
iC j
i
j
C j 1
xi , y j {0,1}
Cj C
Programming Disjoint Habitat Patches
1
n
o
m
q
p
r
Option 1:
xn xm , xn xo , xn x p , xn xq , xn xr ,
xm xo , xm x p , xm xq , xm xr ,
xo x p , xo xq , xo xr ,
x p xq , x p xr , and
xq xr
Option 2:
xn xm xo x p xq xr 6 z1
(the credit goes to Liam Stacey, CFR grad student for
conceiving this construct)
A Stronger Formulation for the Minimum
Contiguous Habitat Size Problem
Minci xi
i
subject to :
a x
i i
xi y j
A
i
y
j
xi
iI
i
Cj yj
Cj C
jPi
x
iC j
x y
iC j
i
j
C j 1
xi , y j {0,1}
Cj C
i C j and C j C
Efficient Site Selections Near the Dick Young Forest
Preserve, IL at Different Contiguity Thresholds
Efficient contiguous habitat protection
50.00
49.90
49.80
Cost (million $)
49.70
49.60
49.50
49.40
49.30
49.20
49.10
49.00
452
454
456
458
460
462
464
468
466
Cost (mill. $)
Efficient protected habitat area (ha)
20.00
120ha
19.00
18.00
128
133
Protected habitat (ha)
400-450-500ha
150ha
200ha
250-300-350ha
100ha
470
472
Parcel Selection 1
Contiguity Threshold: 250-300-350 ha
Acquisition Cost: $49.91M
Acquisition Area: 460.6 ha
Parcel Selection 2
Contiguity Threshold: 200 ha
Acquisition Cost: $50.00M
Acquisition Area: 460.84 ha
Parcel Selection 3
Contiguity Threshold: 150 ha
Acquisition Cost: $49.99M
Acquisition Area: 468.52 ha
Parcel Selection 4
Contiguity Threshold: 120 ha
Acquisition Cost: $49.95M
Acquisition Area: 469.88 ha
Parcel Selection 5
Contiguity Threshold: 100 ha
Acquisition Cost: $49.97M
Acquisition Area: 471.13 ha
Parcel Selection 6
Parcel
Selection
6+
Contiguity
Threshold:
400-450-500
ha
Contiguity
Threshold:
N/A
Acquisition
Cost: $18.8M
Acquisition
Acquisition Cost:
Area: $49.94M
135.05 ha
Acquisition Area: 430.6 ha
Shape
– Edge-to-Interior Area Ratio –
Perimeter
K p q k p kq 2CB pq
pq
Ktotal ki xi 2 x p xq CBpq
iI
pqE
x p xq pq 1
x p xq 2 pq 0
•Kp+q = combined perimeter of parcels p and q;
•Ktotal = the total combined perimeter of all protected parcels;
•CBpq = length of common boundary between stands P and Q;
•E = the set of adjacent pairs of parcels
•xp = 1 if parcel p is to be selected for conservation,
= 0 otherwise.
•
pq = 1 if both stand P and Q are part
of mature patch.