Geoscience Reference
In-Depth Information
open concentrators. Constraints ( 20.32 ) impose a degree 2 for each concentrator
in the cycle, and cut constraints ( 20.33 ) make sure the cycle is connected (i.e.
disjoint cycles are avoided). Finally, constraint ( 20.34 ) imposes to open the root,
and constraints ( 20.35 )and( 20.36 ) ensure variables are binary.
A variant of the RSP is the Median Cycle Problem (MCP), studied by Labbé
et al. ( 2005a ). In this case, the objective function only contains ring costs, i.e.
Minimize X
fi;jg2E
d ij z ij ;
and the problem incorporates the assignment costs as a budget constraint
X
X
c ij x ij B;
i2V
j2V
for a given maximal budget B.
For larger scale networks, instead of connecting customers directly to con-
centrators, additional resilience to failures can be obtained by interconnecting
customers assigned to the same concentrator through a self-healing ring connected
to the backbone ring of concentrators (sometimes called the federal ring in this
context). Goldschmidt et al. ( 2003 ) study a basic version of this problem, called
the SONET ring assignment problem (SRAP). The problem can be described as a
node-partitioning problem consisting of assigning nodes to local rings and inter-
connecting the local rings by a federal ring. The goal is to minimize the number
of rings needed, while ensuring that the sum of demands between nodes in the
same ring do not exceed the capacity of the ring, and also that the sum of inter-
ring demands does not exceed the capacity of the federal ring. They report results
with an integer programming approach as well as several heuristics for solving the
problem. Note, however, that they do not consider the physical topology of the rings.
As reported by Goldschmidt et al. ( 2003 ), another drawback of this kind of
designs is that many instances are infeasible. Recently, Carroll et al. ( 2013 ) studied
a generalization of both the SRAP and the RSP, called the Ring Spur Assignment
Problem (RSAP). In this problem, the objective is to design a set of bounded
disjoint local rings that are interconnected by a federal ring, like in the SRAP.
The topology of the rings must also be determined. Since no SRAP solution exist
in some real world instances, locations that have insufficient spare capacity or no
possible physical route due to limitations of geography can be connected to local
rings by spurs off the local rings. Spur nodes must be connected to a local ring
by a single edge, like in the RSP. Carroll et al. ( 2013 ) proposed a formulation for
the problem that combines blocks of constraints similar to the formulation above
for the RSP for each local ring, plus additional constraints linking the local rings
together and defining the federal ring. We do not reproduce the formulation here
due to its complexity and large size. Carroll et al. ( 2013 ) also proposed some valid
inequalities and solved the problem with a branch-and-cut algorithm. To the best
Search WWH ::




Custom Search