Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(9)
Access Network
Copper
Decomposition Method
Fixed Cost
multicommodity flow
Network Design
Network Flow
Optical Fiber
Optimization Problem
Related Publications
(1)
Minimum Cost Capacity Installation for Multicommodity Network Flows
Subscribe
Academic
Publications
Benders decomposition for local access network design with two technologies
Benders decomposition for local access network design with two technologies,Discrete Mathematics & Theoretical Computer Science,C. D. Randazzo,Henriqu
Edit
Benders decomposition for local access network design with two technologies
(
Citations: 9
)
BibTex

RIS

RefWorks
Download
C. D. Randazzo
,
Henrique Pacca Loureiro Luna
,
P. Mahey
We have worked with the local
access network
design problem with two cable technologies. This is an
optimization problem
in graphs that consists of linking an origin node to a set of terminal nodes which have a flow demand. There are also a set of Steiner or transshipment nodes which do not have demand. Each arc of the graph has two associated costs: a variable cost depending on the flow through the arc and a
fixed cost
associated with the installation of the arc. Moreover, in each arc we can install one of two available technologies:
optical fiber
or
copper
(we can also use radio links with any other cable technology). Each one of these technologies has different variable and fixed costs. To be more precise, the
fixed cost
of the
optical fiber
is greater than that of the copper, but its variable cost is much smaller. The problem was modeled using a
multicommodity flow
formulation in which we added some structural constraints. This model was used to apply the Benders decomposition method. The structural constraints have the objective of trying to guarantee that the master problem of the Benders decomposition will yield a tree. The Benders subproblems are trivial
network flow
problems. The dual variables have commodity meaningfull values and are evaluated in a systematic form. The algorithm was implemented in C++ with CPLEX 3.0 callable library. We have tested the algorithm with some test instances obtained by a generator of problems that we developed.
Journal:
Discrete Mathematics & Theoretical Computer Science  DMTCS
, vol. 4, no. 2, pp. 235246, 2001
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.emis.de
)
(
www.informatik.unitrier.de
)
(
www.dmtcs.org
)
(
dmtcs.loria.fr
)
More »
Citation Context
(4)
...Two closely related papers are by Randazzo et al. [
19
] and Mateus and Franqueira [17]...
...Randazzo et al. [
19
] consider a local access network design problem with two technologies...
Fatma Gzara
,
et al.
Telecommunications network design with multiple technologies
...Benders decomposition could be used when solving many structured problems, such as network design, by formulating them as a linear programming model [
10
]...
Ehab Z. Elfeky
,
et al.
Partial decomposition and parallel GA (PDPGA) for constrained optimiz...
...Some references in this area and related problems are [7,
8
]...
Hector Cancela
,
et al.
Designing lowcost access network topologies
...On the other hand, some others researches [11, 15, 22, 35,
45
] focus on uncapacited problems and try to define the right capacity which leads to the minimum total cost...
...Some studies choose Branch and Cut techniques [11, 22, 36], Column Generation in [47], Column and Cut Generation in [43], Lagrangian and Linear Relaxation in [55], Tabu Search in [23, 55], Simulated Annealing in [25] and, as our work, Benders Decomposition in [10, 21, 34, 35,
45
]...
...Benders decomposition thus leads consequently to certain improvement in terms of algorithm convergence and also in terms of rapidity, which justifies the fact that it has been used in a significant number of applications [6, 8, 10, 21, 26, 34, 35,
45
]...
Bernard Fortz
,
et al.
Decomposition Methods for the Optimization of Survivable Telecommunica...
References
(16)
An integer linear programming approach to the steiner problem in graphs
(
Citations: 80
)
Y. P. Aneja
Journal:
Networks
, vol. 10, no. 2, pp. 167178, 1980
Partitioning procedures for solving mixedvariables programming problems
(
Citations: 780
)
J. F. Benders
Journal:
Numerische Mathematik  NUMER MATH
, vol. 4, no. 1, pp. 238252, 1962
A note on two problems in connection with graphs
(
Citations: 3271
)
E.W. Dijkstra
Published in 1959.
The engine scheduling problem in a railway network
(
Citations: 22
)
M. G. Bushell Florian
,
J. Ferland
,
G. Guerin
,
L. Nastansky
Journal:
Informs Journal on Computing  INFORMS
, 1976
Multicommodity Distribution System Design by Benders Decomposition * † ‡
(
Citations: 209
)
A. M. Geoffrion
Sort by:
Citations
(9)
Telecommunications network design with multiple technologies
Fatma Gzara
,
Erhan Erkut
Journal:
Telecommunication Systems  TELSYS
, vol. 46, no. 2, pp. 149161, 2011
A hybrid algorithm for capacitated plant location problem
MingChe Lai
,
Hansuk Sohn
,
Chunkuan Chiang
Journal:
Expert Systems With Applications  ESWA
, vol. 37, no. 12, pp. 85998605, 2010
Benders decomposition applied to multicommodity, multimode distribution planning
(
Citations: 3
)
Ozan Çakir
Journal:
Expert Systems With Applications  ESWA
, vol. 36, no. 4, pp. 82128217, 2009
Partial decomposition and parallel GA (PDPGA) for constrained optimization
Ehab Z. Elfeky
,
Ruhul A. Sarker
,
Daryl L. Essam
Conference:
IEEE International Conference on Systems, Man, and Cybernetics  SMC
, pp. 220227, 2008
A survey on benders decomposition applied to fixedcharge network design problems
(
Citations: 40
)
Alysson M. Costa
Journal:
Computers & Operations Research  CoR
, vol. 32, no. 6, pp. 14291450, 2005