篇名 | A linearization method for quadratic minimum spanning tree problem |
---|---|
卷期 | 10:4 |
作者 | Jing-Rung Yu 、 Ren-Xiang Shi 、 Her-Jiun Sheu |
頁次 | 287-291 |
關鍵字 | Linear integer programming 、 Network optimization 、 Quadratic minimum spanning tree 、 EI 、 SCI 、 SCIE 、 Scopus |
出刊日期 | 200812 |
The crisp and fuzzy quadratic minimum spanning tree (Q-MST) problem can be formulated as a linear model, and thus, the global optimum can be obtained by the proposed method. Conventionally, the Q-MST problem, which contains a quadratic term in the objective function, is solved by genetic algorithm and other heuristic methods. However, these methods cannot guarantee to obtain a global optimal solution. To address this issue, the proposed method transforms the quadratic term into linear formulations for crisp and fuzzy Q-MST problems, and yields the global optimum solutions by linear integer programming. Two examples are given to demonstrate the proposed method in greater detail.