Zinchenko, YuriySong, Haotian2016-09-192016-09-1920162016Song, H. (2016). On a 2-path problem (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/27172http://hdl.handle.net/11023/3314An electric power supplier needs to build a transmission line between 2 jurisdictions. Ideally, the design of the new electric power line would be such that it optimizes some user-defined utility function, for example, minimizes the construction cost or the environmental impact. Due to reliability considerations, the power line developer has to install not just one, but two transmission lines, separated by a certain distance from one to another, so that even if one of the lines fails, the end user will still receive electricity along the second line. We discuss how such a problem can be modelled and prove the general graph-based problem to be NP-hard. At the same time, we propose a polynomial-time approximation scheme to handle this problem. Although the worst-case performance of the latter scheme is not fully understood yet, we note that under two mild practical assumptions, the scheme yields the optimal solution to the original problem. The novel scheme appears to be extremely efficient numerically. Our implementation scheme vastly outperforms more conventional solution methods, such as mixed-integer based models. In turn, this allows us to solve realistically sized problems on graphs nearing a hundred thousand nodes.engUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.Computer ScienceEngineering--Operations Researchmaster thesis10.11575/PRISM/27172