A two-level location-allocation problem in designing local access fiber optic networks
- Authors
- Park, Gigyoung; Lee, Youngho; Han, Junghee
- Issue Date
- 11월-2014
- Publisher
- PERGAMON-ELSEVIER SCIENCE LTD
- Keywords
- Access networks; Fiber optic access networks; MIP-based tree partitioning heuristic; Mixed integer programming; Reformulation- linearization technique (RLT)
- Citation
- COMPUTERS & OPERATIONS RESEARCH, v.51, pp.52 - 63
- Indexed
- SCIE
SCOPUS
- Journal Title
- COMPUTERS & OPERATIONS RESEARCH
- Volume
- 51
- Start Page
- 52
- End Page
- 63
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/96903
- DOI
- 10.1016/j.cor.2014.05.005
- ISSN
- 0305-0548
- Abstract
- This paper deals with a two-level facility location-allocation problem on tree topology arising from the design of access networks. The access network design problem seeks to find an optimal location of switch and allocation of demands such that the total cost of switch and fiber cable is minimized, while satisfying switch port constraint, switch capacity constraint, and no-split routing constraint. The problem is formulated as a mixed-integer programming model and alternative formulations are developed by the reformulation-linearization technique (RLT) for improving computational effectiveness. By exploiting the tree structure of the problem, we develop some valid inequalities that have complementary strength and devise separation problems for finding effective valid inequalities that cut off fractional LP solutions. Also, we develop an effective MIP-based tree partitioning heuristic for finding good quality solutions for large size problems. Computational results demonstrate the efficacy of the valid inequalities and the proposed heuristic. (C) 2014 Elsevier Ltd. All rights reserved.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - College of Engineering > School of Industrial and Management Engineering > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.