Geoscience Reference
In-Depth Information
A branch and bound can only be used as soon as increasingly tight bounds
are built for C.
x
/ on a box
X
D
.X
1
;:::;X
p
/. Each X
i
is a rectangle X
i
D
.Œa
i
;b
i
;Œc
i
;d
i
/ where the i-th facility is allowed to be located. One has then on
a given box
X
Z
c.a;
x
/d.a/
Z
min
x
2
X
C.
x
/
D
min
min
x
2
X
c.a;
x
/d.a/:
x
2
X
A
A
For the general function c.a;
x
/
D
.c
1
.a;x
1
/;c
2
.a;x
2
/;:::;c
p
.a;x
p
//; as
in (
6.8
), with non-decreasing function of c
i
.a;x
i
/
8
i, it can be derived further to
Z
c.a;
x
/d.a/
D
Z
min
x
1
2X
1
c
p
.a;x
p
/
d.a/
min
x
2
X
c
1
.a;x
1
/;:::; min
x
p
2X
p
A
A
min
x
1
2X
1
'
p
.
k
a
x
p
k
/
d.a/;
D
Z
'
1
.
k
a
x
1
k
/;:::; min
x
p
2X
p
A
where, as in (
6.1
), c
i
.a;x
i
/
D
'
i
.
k
a
x
i
k
/ for a non-increasing function '
i
of the
distance for all i. This leads to
x
2
X
C.
x
/
Z
'
1
.max
x
1
2X
1
k
a
x
p
k
/
d.a/
min
k
a
x
1
k
/;:::;'
p
. max
x
p
2X
p
A
D
Z
'
1
. max
x
1
2ext.X
1
/
k
a
x
p
k
/
d.a/;
k
a
x
1
k
/;:::;'
p
. max
x
p
2ext.X
p
/
A
where ext.X
i
/ denotes the set of vertices of the box X
i
. For the particular case of an
all-or-nothing covering function as given in (
6.2
), the above integral simplifies to
Z
d.a/;
I.
X
/
where the set I.
X
/
D
S
iD1
I
i
.X
i
/ with I
i
.X
i
/
Df
a
2
A
j
c
i
.a;x
i
/
D
1
8
x
i
2
ext.X
i
/
g
,i.e.I
i
.X
i
/ is the set of points a such that, for facility i; all points in X
i
cover a (the gray region in Fig.
6.2
). For an easier description of the set I
i
.X
i
/ one
can consider its inscribed circle, I
i
.X
i
/ asshowninFig.
6.2
.
This leads to
x
2
X
C.
x
/
Z
Z
Z
X
p
X
p
min
d.a/
d.a/
d.a/:
S
iD1
I
i
.X
i
/
I
i
.X
i
/
T
I
j
.X
j
/
I
i
.X
i
/
iD1
i;jD1
i<j
