New Integer Programming Algorithms for solving the Network Design Problems
- 주제(키워드) Mixed-Integer Programming , Access Network Design , Reformulation-Linearization Technique , Tree Partitioning Programming
- 발행기관 고려대학교 정보경영공학전문대학원
- 지도교수 이홍철
- 발행년도 2015
- 학위수여년월 2015. 2
- 학위구분 박사
- 학과 정보경영공학전문대학원 정보경영공학과
- 세부전공 경영공학전공
- 원문페이지 135 p
- 실제URI http://www.dcollection.net/handler/korea/000000058147
- 본문언어 영어
- 제출원본 000045828383
초록/요약
In this paper, we present two problems arising when deploying multimedia access networks and develop solution procedures for each problem by exploiting the inherent combinatorial structure. The both problems is concerned with two-level location allocation problems for constructing a physical access network. The first one is formulated as a mixed-integer programming and the other one is formulated as a nonlinear mixed integer programming. First, 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. Next, we deal with a multimedia access network design problem with nonlinear quality of service (QoS) constraints. The design of access network seeks an optimal location of two-level switches and allocation of demands satisfying the prescribed level of QoS. The problem is formulated as a two-level hierarchical location-allocation model on tree topology with nonlinear QoS constraints. Dealing with the inherent complexity of nonlinear QoS constraints, an effective tabu search algorithm is developed such that switch installation strategies determine the number of switches, while reassignment moves evaluate neighborhood solutions. Computational results exhibit the efficacy of the proposed algorithm.
more목차
1 Introduction 1
1 Access Network Design Problem . . . . . . . . . . . . 1
2 Two-level Location-allocation Problem . . . . . . . . 4
3 A tree topology infrastructure in a Seoul Metro Area 8
4 Contribution of the Thesis . . . . . . . . . . . . . . . 10
5 Outline of the Thesis . . . . . . . . . . . . . . . . . . 13
2 A two-level location-allocation problem in designing
local access fiber optic networks 14
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Formulation . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Heuristic procedure . . . . . . . . . . . . . . . . . . . . 45
4 Computational Results . . . . . . . . . . . . . . . . . . 51
3 A tabu search algorithm for solving a nonlinear network
optimization problem of emerging multimedia
access networks 65
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 65
2 Problem Formulation . . . . . . . . . . . . . . . . . . . 73
3 Tabu Search Algorithm . . . . . . . . . . . . . . . . . . 80
3.1 Generating an Initial Solution . . . . . . . . . . 82
3.2 Improving the Initial Solution . . . . . . . . . . 86
3.3 Implementation Strategy . . . . . . . . . . . . . 97
4 Computational Results . . . . . . . . . . . . . . . . . . 101
4 Conclusion 115
