Geoscience Reference
In-Depth Information
One can address the problem of finding (an approximation to) the set of Pareto-
optimal solutions to (
6.21
), as done for other problems in Blanquero and Carrizosa
(
2002
), Romero-Morales et al. (
1997
). Alternatively, one can consider one of the
criteria as constraint, and address instead the problem of minimizing the covering
C.
x
/ keeping the facility-facility cover C
F
.
x
/ below a threshold limit ı
W
minimize C.
x
/
subject to C
F
.
x
/
ı
x
2
(6.22)
S
:
Assuming for C
F
the model given by (
6.18
), problem (
6.22
) amounts to finding p
points x
1
;:::;x
p
so that they are at a distance at least
'
F
1
.ı/ from each other
and the covering C is minimized. This is the approach proposed e.g. in Berman and
Huang (
2008
), in which undesirable facilities are located (on a network) so as no
facilities are allowed to be closer than a pre-specified distance.
6.3
Computational Approach
While nowadays computational tools allow one to address
discrete
p-facility
problems with a very large p, e.g. Avella and Boccia (
2007
), Avella et al. (
2006
),
nonconvex continuous location problems, as those addressed here, can only be
solved exactly for a very small number of facilities to be located. The most popular
and most effective technique is a geometric branch and bound, which can already be
found under the name of Big Square Small Square (BSSS) (Hansen et al.
1985
), and
later modified by a number of authors (Blanquero and Carrizosa
2008
; Drezner and
Suzuki
2004
;Plastria
1992
; Schöbel and Scholz
2010
), coining names such as BTST
(Big Triangle Small Triangle) or Big Cube Small Cube. See Drezner (
2012
)fora
recent review of such variants. In our case the search space is the set of p rectangles
for the p facilities, that gives a multi-dimensional interval, also called a box. The
main steps of the branch and bound are as usual: a list of boxes is handled, each box
being associated with a subproblem, namely, the covering location problem in which
facilities are to be located within such box; at each step one box is selected from
the list and divided into smaller boxes. Bounds on the optimum over the subboxes
are calculated, so that boxes which are found not to contain the global optimum are
removed, while the rest is saved for further processing. The branching and bounding
rules are iterated until the gap between the underestimation and underestimation of
the optimal value is smaller than the prescribed accuracy.
In our implementation, selection of the next box is done by the smallest lower
bound, and the division rule is defined by halving both sides of the largest rectangle
into four equal sized rectangles. An upper bound on the minimum is calculated
evaluating the objective function at the midpoint of the selected box. In what
follows, a bounding procedure, valid for arbitrary pdfs, is discussed.
