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
Search WWH ::




Custom Search