Geoscience Reference
In-Depth Information
Constraint (
4.10
) eliminates the solutions with no open facility. Constraints (
4.11
)
and the objective function (
4.9
) ensure that all demand points are served by a facility
within the smallest possible distance.
A semi-relaxation of this formulation, which is obtained by removing the
binary restriction on the y variables, provides the best known lower bound for the
p-center problem. This lower bound can be obtained by solving a finite series of LP
problems, which are the LP relaxations of the set covering problems. Elloumi et al.
(
2004
) also provided an exact algorithm that combines the important properties of
the algorithms of Minieka (
1970
) and Ilhan and Pınar (
2001
). Their algorithm uses
the two-phase idea and a binary search strategy similar to the algorithm by Ilhan and
Pınar (
2001
), but restricts the set of radius values to solve the set covering problems
with the finite radius set R as in Minieka (
1970
).
Calik and Tansel (
2013
) developed new IP formulations and a new exact
algorithm based on the decomposition of their models for solving the p-center
problem. They associated a binary variable
u
k
with r
k
, for each k
2f
1;:::;K
g
.
In particular,
u
k
is equal to 1 if r
k
is selected as the optimal value and 0 otherwise.
Initially, they proposed the following formulation:
X
K
Minimize
r
k
u
k
(4.13)
kD1
subject to
(
4.5
), (
4.6
),
X
y
i
u
k
8
j
2
J;k
D
1;:::;K;
(4.14)
iWd
ji
r
k
K
X
u
k
D
1;
(4.15)
kD1
u
k
2f
0;1
g
k
D
1;:::;K:
(4.16)
Constraint (
4.15
) sets exactly one of the variables
u
k
to 1 and the corresponding
r
k
value is selected as the optimal value according to the objective function (
4.13
).
Constraints (
4.14
) ensure that each customer is served within the selected radius
by at least one facility. Constraints (
4.16
) are binary restrictions. The authors
proposed a tightened formulation by using a relationship between their formulation
and the formulation proposed by Elloumi et al. (
2004
). In this formulation,
constraints (
4.14
) are replaced with constraints (
4.17
)givenbelow:
X
X
k
y
i
u
q
;
8
j
2
J;k
D
1;:::;K:
(4.17)
qD1
iWd.i;j/r
k
The semi relaxations of these formulations, in which the binary restriction of
the y-variables are removed, provide the tight lower bound obtained by Elloumi
