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
iI
i i
s.t.
c x
iI
i i
x
iS 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
iS j
i
 yj
j  J
• Our objective function will become:
Max
y
jJ
j
Maximal Species Representation
cont.
• Our mathematical program becomes:
Max
y
jJ
j
s.t.:
c x
iI
i i
x
iS 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
jPi
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
iC 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
iC 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
jPi
x
iC j
x  y
A cluster must be protected if
each parcel that makes up the
cluster is protected
Protected area
iC 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
Minci xi
i
subject to :
a x
i i
xi  y j
A
i
y
j
 xi
 iI
i
 Cj yj
 Cj C
jPi
x
iC j
x  y
iC 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
iI
pqE
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.