A Branch-and-Bound Algorithm to Solve a Multi-level Network Optimization Problem |
| |
Authors: | F R B Cruz G R Mateus J MacGregor Smith |
| |
Institution: | (1) Departamento de Estatística, Universidade Federal de Minas Gerais, 31270-901 – Belo Horizonte – MG, Brazil;(2) Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, 31270-901 – Belo Horizonte – MG, Brazil;(3) Department of Mechanical & Industrial Engineering, University of Massachusetts, Amherst, MA, 01003, U.S.A |
| |
Abstract: | Multi-level network optimization problems arise in many contexts such as telecommunication, transportation, and electric power systems. A model for multi-level network design is formulated as a mixed-integer program. The approach is innovative because it integrates in the same model aspects of discrete facility location, topological network design, and dimensioning. We propose a branch-and-bound algorithm based on Lagrangian relaxation to solve the model. Computational results for randomly generated problems are presented showing the quality of our approach. We also present and discuss a real world problem of designing a two-level local access urban telecommunication network and solving it with the proposed methodology. |
| |
Keywords: | network design multi-level networks topological network design location problems Steiner problems in graphs |
本文献已被 SpringerLink 等数据库收录! |
|