On a 2-path problem
Abstract
An 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.
Description
Keywords
Computer Science, Engineering--Operations Research
Citation
Song, 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/27172