DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Park, Sung-Soo | - |
dc.contributor.advisor | 박성수 | - |
dc.contributor.author | Kim, Ki-Hyun | - |
dc.contributor.author | 김기현 | - |
dc.date.accessioned | 2011-12-14T04:09:24Z | - |
dc.date.available | 2011-12-14T04:09:24Z | - |
dc.date.issued | 2009 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=308675&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/40826 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 산업및시스템공학과, 2009.2, [ ii, 32 p. ] | - |
dc.description.abstract | In this thesis, we solve the Steiner tree problem in graph using column generation technique. This algorithm is based on integer programming formulation for directed graph and based on path variables which can be generated in polynomial time. We improve the performance of the algorithm by adopting row-generation technique and stabilized column generation technique. We compare the performance of the algorithm with the branch-and-cut algorithm based on cut set constraint. The LP relaxations of our formulation and the cut-set based formulation provide the same lower bound on the optimal value. We compare the performance of both approaches in computation time, the number of generated cuts and columns. We use preprocessing for large test problems to reduce the problem size considerably. Test results on SteinLib benchmark problems are reported. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | Steiner tree | - |
dc.subject | column generation | - |
dc.subject | stabilized column generation | - |
dc.subject | integer programming | - |
dc.subject | linear programming | - |
dc.subject | 스타이너 나무 | - |
dc.subject | 열 생성 기법 | - |
dc.subject | 정수계획법 | - |
dc.subject | 선형계획법 | - |
dc.subject | Steiner tree | - |
dc.subject | column generation | - |
dc.subject | stabilized column generation | - |
dc.subject | integer programming | - |
dc.subject | linear programming | - |
dc.subject | 스타이너 나무 | - |
dc.subject | 열 생성 기법 | - |
dc.subject | 정수계획법 | - |
dc.subject | 선형계획법 | - |
dc.title | Path based column generation approach for the Steiner tree problem | - |
dc.title.alternative | 열 생성 기법을 이용한 스타이너 나무 문제에 관한 연구 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 308675/325007 | - |
dc.description.department | 한국과학기술원 : 산업및시스템공학과, | - |
dc.identifier.uid | 020073052 | - |
dc.contributor.localauthor | Park, Sung-Soo | - |
dc.contributor.localauthor | 박성수 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.