Benders decomposition for local access network design with two technologies
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 dem...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2001-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/288/pdf |
| _version_ | 1827323885773651968 |
|---|---|
| author | C. D. Randazzo H. P. L. Luna P. Mahey |
| author_facet | C. D. Randazzo H. P. L. Luna P. Mahey |
| author_sort | C. D. Randazzo |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:00:52Z |
| format | Article |
| id | doaj.art-a6881b6d7c97480abfa081d3554a0335 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:00:52Z |
| publishDate | 2001-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-a6881b6d7c97480abfa081d3554a03352024-03-07T15:04:11ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502001-01-01Vol. 4 no. 210.46298/dmtcs.288288Benders decomposition for local access network design with two technologiesC. D. Randazzo0H. P. L. Luna1P. Mahey2Departamento de Ciência da Computação [Minas Gerais]Departamento de Ciência da Computação [Minas Gerais]Departamento de Ciência da Computação [Minas Gerais]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.https://dmtcs.episciences.org/288/pdfnetwork designbenders decomposition[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | C. D. Randazzo H. P. L. Luna P. Mahey Benders decomposition for local access network design with two technologies Discrete Mathematics & Theoretical Computer Science network design benders decomposition [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Benders decomposition for local access network design with two technologies |
| title_full | Benders decomposition for local access network design with two technologies |
| title_fullStr | Benders decomposition for local access network design with two technologies |
| title_full_unstemmed | Benders decomposition for local access network design with two technologies |
| title_short | Benders decomposition for local access network design with two technologies |
| title_sort | benders decomposition for local access network design with two technologies |
| topic | network design benders decomposition [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/288/pdf |
| work_keys_str_mv | AT cdrandazzo bendersdecompositionforlocalaccessnetworkdesignwithtwotechnologies AT hplluna bendersdecompositionforlocalaccessnetworkdesignwithtwotechnologies AT pmahey bendersdecompositionforlocalaccessnetworkdesignwithtwotechnologies |