Download the full-sized PDF of Application of ILP-based Heuristic and Dantzig-Wolfe Decomposition to Solve the Multi-period Survivable Network Augmentation ProblemDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Application of ILP-based Heuristic and Dantzig-Wolfe Decomposition to Solve the Multi-period Survivable Network Augmentation Problem Open Access


Other title
Multi-period network planning
Integer linear programming
Shared backup path protection
Type of item
Degree grantor
University of Alberta
Author or creator
Wang, Yali
Supervisor and department
Doucette, John (Department of Mechanical Engineering)
Examining committee member and department
Zuo, Ming (Department of Mechanical Engineering)
Tian, Zhigang (Department of Mechanical Engineering)
Doucette, John (Department of Mechanical Engineering)
Department of Mechanical Engineering
Engineering Management
Date accepted
Graduation date
2016-06:Fall 2016
Master of Science
Degree level
Multi-period planning is a cost efficient method for designing backbone networks and has been widely used for many years. To ensure the quality of the network service, network survivability has also become a critical requirement in network planning and design. The purpose of this thesis is to take multi-period incremental demands, network survivability and economies of scale into account, and to focus on the optimization of network topology design, working demand routing, and spare capacity allocation. To fulfill this objective, an integer linear programming (ILP) model for a multi-period survivable network augmentation (MPSNA) problem is developed, and the shared backup path protection (SBPP) mechanism is used. However, the MPSNA problem is very time-consuming to solve even for a very small network. To overcome this difficulty, a four-stage ILP-based heuristic method is developed to solve the MPSNA problem. In addition, the effectiveness of the implementation of the Dantzig-Wolfe decomposition for solving the MPSNA is also investigated.
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
Citation for previous publication
Y. Wang, J. Doucette, “ILP-based Heuristic Method for the Multi-period Survivable Network Augmentation Problem,” Reliable Network Design and Modeling (RNDM 2016), accepted: 17-June, 2016.

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1368443
Last modified: 2016:11:16 16:15:00-07:00
Filename: Wang_Yali_201607_M.Sc..pdf
Original checksum: 0641d60c2762ed4ede26379997985500
Well formed: true
Valid: true
File title: Microsoft Word - Yali Wang-M.Sc. thesis-final-Jun29 -new
File author: xihui2
Page count: 134
Activity of users you follow
User Activity Date