Geoscience Reference
In-Depth Information
X
d
j
x
ij
q
i
y
i
i
2
I;
(20.3)
j2J
x
ij
y
i
i
2
I; j
2
J;
(20.4)
x
ij
2f
0;1
g
i
2
I; j
2
J;
(20.5)
y
i
2f
0;1
g
i
2
I:
(20.6)
Constraints (
20.2
) ensure that each end-user is linked to one of the concentrators.
Constraints (
20.3
) guarantee that no concentrator will serve more end-users than
its capacity. Assignment of end-users to open concentrators only is ensured by
constraints (
20.4
). These constraints are redundant in the integer program but
improve considerably the linear relaxation of the problem. Finally, constraints (
20.5
)
and (
20.6
) ensure that the variables are binary.
Note that this problem is also often called the
Capacitated Facility Location
Problem with Single-Source Constraints
as it becomes the classical Capacitated
Facility Location Problem if the binary requirement on x
ij
variables is relaxed.
In the context of telecommunications networks, any node is a potential concen-
trator location, hence I
D
J. In this case, variables y
i
are sometimes replaced
by x
ii
.
Many heuristic methods have been proposed to solve that problem, starting with a
Lagrangian relaxation algorithm proposed by Pirkul (
1987
). Holmberg et al. (
1999
)
embedded the Lagrangian relaxation approach in a branch-and-bound framework,
leading to a very efficient exact algorithm. More recently, Díaz and Fernández
(
2002
) proposed a branch-and-price algorithm for that problem, and Contreras and
Díaz (
2008
) developed a scatter search approach to provide upper bounds for the
optimal solution of the problem.
Ceselli et al. (
2009
) study different variants of the problem and propose a set-
partitioning reformulation that is used in a general branch-and-price framework.
Gouveia and Saldanha da Gama (
2006
) proposed a discretized model for the unit
demand case. The model is also used for an extension of the problem where facilities
have different possible capacities available (the so-called unit-demand capacitated
concentrator location problem with modular interfaces). They also strengthen the
model with additional valid inequalities. Correia et al. (
2010
) also used similar
discretization technique for the case of modular link capacities.
More realistic models for telecommunications have end-to-end demands, instead
of aggregated demands by end-user as assumed in the model above. The resulting
problems become quadratic and can be seen as special cases of the Single
Allocation Hub Location Problem. Labbé and Yaman (
2006
) made a polyhedral
analysis of formulations obtained by linearization of the quadratic terms, proposed
valid inequalities to strengthen the formulation and solve it by a branch-and-cut
algorithm. For the uncapacitated case, Labbé and Yaman (
2008
) extended their study
by adding routing costs. They also did a polyhedral analysis of formulations and
proposed a Lagrangian relaxation heuristic. Labbé et al. (
2005b
) study the variant