DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Park, Sung-Soo | - |
dc.contributor.advisor | 박성수 | - |
dc.contributor.author | Lee, Dong-Joon | - |
dc.contributor.author | 이동준 | - |
dc.date.accessioned | 2011-12-14T04:18:31Z | - |
dc.date.available | 2011-12-14T04:18:31Z | - |
dc.date.issued | 1994 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=69476&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/41433 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 산업공학과, 1994.2, [ 39 p. ] | - |
dc.description.abstract | This thesis considers a clique partitioning problem where the size of cliques is restricted within the prescribed range. This problem is to partition a graph into cliques such that the total sum of the edge weights within each clique is maximized. The problem appears in several applications, including GT cell formation problem, integrated circuit layout problem, and clustering problem, etc. We give a 0-1 integer programming formulation of the problem and use the branch-and-cut approach to solve it. Compared to the traditional branch-and-bound approach, the branch-and-cut approach can save the computational efforts needed to solve hard combinatorial optimization problems by embedding strong cutting planes within the branch-and-bound scheme. We used some valid inequalities for the convex hull of the integral feasible solutions of the problem as cutting planes. The algorithm was tested on several randomly generated problems and real-world problems found in the literature. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.title | Solving the clique partitioning problem with clique size constraints | - |
dc.title.alternative | 클릭 크기 제약을 가진 클릭 분할 문제에 관한 연구 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 69476/325007 | - |
dc.description.department | 한국과학기술원 : 산업공학과, | - |
dc.identifier.uid | 000923332 | - |
dc.contributor.localauthor | Park, Sung-Soo | - |
dc.contributor.localauthor | 박성수 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.