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.
본 논문은 클릭의 크기에 제약이 있는 클릭 분할 문제를 정의하고 그에 대한 해법을 제시하고 있다. 이 문제는 그래프를 하나 이상의 클릭으로 분할할 때 클릭의 크기가 정해진 조건을 만족하도록 하면서 각 클릭에 포함 된 호들의 가중치의 합을 최대화하는 문제이다. 이 문제는 그룹테크놀로지, 집적 회로 설계 그리고 클러스터링등의 문제에 응용될 수 있다.
이 조합 최적화 문제는 0-1 정수계획 문제로 모형화가 가능하며 분지 및 절단 기법이 그 해법으로 제시되었다. 이 기법은 절단 평면의 효율적인 사용으로 위 문제를 분지 및 한계 기법으로 접근할 때의 필요한 노력과 시간을 감소시켜 준다. 이 기법의 구현을 위하여 정수계획 문제의 가능해들이 정의하는 볼록집합의 성질을 분석하고 비정수해를 절단할 수 있는 적법한 부등식을 제시하였다.
위 기법으로 몇 개의 실제 응용 문제들과 무작위로 추출한 데이터로 이루어진 문제들에 대해 시험해 본 결과 모두 적당한 시간내에 해결할 수 있었다. 따라서 이 기법은 제안된 문제를 풀기위한 적당한 대안이라고 할 수 있다.
