Recent successes in the resolution of large-scale integer programming (IP) problems are based on the polyhedral studies which can yield tight linear programming (LP) relaxations. This thesis considers three basic combinatorial optimization problems with polyhedral viewpoints and presents results that are useful to solve many potential applications. They are the precedence-constrained knapsack problem, the edge-weighted maximal clique problem, and the extended node packing problem. After presenting results on those problems, we consider an application of the results to solve a hard clustering problem arising in the design of telecommunication networks.
The precedence-constrained knapsack problem is the knapsack problem with precedence constraints imposed on the set of variables. The modification of the cover inequality for the usual knapsack problem is presented. Then a lifting procedure is presented which can strengthen the modified cover inequality. The proposed lifting procedure is computationally very simple and can produce much stronger inequality than the original one. The strength of the modified cover inequality lifted by the procedure is discussed and the problem of finding optimal order of lifting is addressed and solved. The natural LP relaxation is analyzed and it is shown that its fractional vertices can be cut off by the modified cover inequalities. Finally a lifting heuristic to further strengthen the inequality is proposed.
The edge-weighted maximal clique problem finds a clique of maximum weight whose size is less than or equal to a prespecified number in the complete graph. The problem is analyzed by using an extended formulation with additional variables. Classes of facets are proposed for the extended formulation and it is compared with the natural formulation using projection method. Also by using the projection, new facets are proposed for the polytope associated with the natural formulation. To investigate the empirical performance of the extended formulation, a cutting-plane algorithm is proposed and tested. The results show that the algorithm can solve much larger problem instances than that using the natural formulation.
The extended node packing problem is a generalization of the weighted node packing problem. The problem considers both node and edge weights. For the problem, we present classes of facets and show they can imply various strong valid inequalities of the node packing polytope. By using the results, we present a compact formulation of the node packing problem on the t-perfect graph.
Finally, we present a model and an algorithm for the clustering problem arising in the design of telecommunication networks. Various modeling issues are discussed and a formulation based on the column generation is given. The column generation subproblem is analyzed using the results on the models mentioned above. We propose a column generation algorithm for the problem with the subproblem solved by the branch-and-cut. The algorithm is tested on the real problem data.
최근의 대형 정수계획문제의 성공적인 해결은 강력한 선형완화식을 가능하게 하는 다면체적 연구에 기반하고 있다. 본연구에서는 먼저 세 가지 기본적인 조합최적화문제를 다면체적 관점에서 고찰하고 다양한 응용문제에 적용될 수 있는 결과들을 제시한다. 본연구에서 다루는 문제는 우선순위 제약이 있는 배낭문제, 호에 가중치가 주어진 최대 클릭문제와 확장된 독립집합문제이다. 이 문제들에 대한 결과를 제시한 후 통신망의 설계에서 나타나는 복잡한 클러스터링 문제에 대한 응용을 제시한다.
우선순위제약이 있는 배낭문제는 일반적인 배낭문제에서 변수들에 우선순위제약이 주어진 문제이다. 먼저 일반적인 배낭문제에 대한 커버(cover)부등식을 본문제에 맞게 수정 제시한다. 그리고, 수정된 부등식을 강화할 수 있는 리프팅(lifting)절차를 제시한다. 제안된 리프팅절차는 계산방법이 매우 단순하나 원부등식보다 매우 강화된 부등식을 구할 수 있게 해준다. 리프팅된 부등식의 성질을 다면체적 측면에서 분석하고, 최적인 리프팅 순서를 구하는 문제를 다루었으며 또한 그 해를 제시하였다. 본문제에 대한 선형완화식을 분석하고 부분정점해들이 본연구에서 제시된 커버부등식에 의해 제거될 수 있음을 보였다. 마지막으로 부등식을 좀더 강화할 수 있는 또다른 리프팅 절차를 제시한다.
호에 가중치가 주어진 최대 클릭문제는 완전그래프상에서 최대의 가중치를 가지는 크기가 제한된 클릭을 구하는 문제이다. 이문제는 추가적인 변수를 도입하여 얻어진 확장된 수리모형을 이용하여 분석한다. 제안된 수리모형에 대해 다면체적 연구를 통한 부등식들을 제시하고 사영(projection) 기법을 통하여 원래의 수리모형과 비교하였다. 또한 사영기법을 이용하여 원모형에 대한 새로운 부등식들을 제안한다. 본연구에서 제시된 확장 모형의 실제적인 성능을 조사하기 위하여 절단평면 알고리듬을 제시하고 시험하였다. 계산결과 제시된 알고리듬이 원모형에 기초한 알고리듬보다 대형의 문제를 효과적으로 해결할 수 있음을 보였다.
확장된 독립집합문제는 가중치 있는 독립집합문제의 일반화된 문제이다. 이문제는 마디 및 호에 주어진 가중치를 동시에 고려한다. 이문제에 대하여 부등식들을 제시하고 제시된 부등식들이 원래에 독립집합문제에 대해 알려져 있는 많은 부등식들을 내포하고 있음을 보인다. 이러한 결과를 이용하여 t-완전그래프상에서 독립집합문제에 대한 간결한 수리모형을 제시한다.
마지막으로 통신망의 설계에서 나타나는 클러스터링문제에 대한 모형과 해법을 제시한다. 문제의 모형화와 관련된 다양한 문제들을 고려하고 열생성기법에 근거한 수리모형을 제시한다. 열생성을 위한 부문제는 위에서 제시한 문제들에 대한 결과를 이용하여 분석되었다. 제안된 모형에 대하여 열생성기법을 이용한 알고리듬을 제안하고 실제문제에 대한 계산결과를 제시하였다.
