In this thesis, we consider the Chv$\acute{a}$tal-Gomory inequalities for integer programming problem. Although the Chv$\acute{a}$tal-Gomory inequalities motivated the cutting plane approaches for combinatorial optimization problems, researches focusing on the practical aspects of the Chv$\acute{a}$tal-Gomory inequalities seem to be limited. The goal of the research is to provide efficient separation procedures to get strong Chv$\acute{a}$tal-Gomory inequalities for even multiple constraints. As a result, we provide several standard forms of strong rank 1 Chv$\acute{a}$tal-Gomory inequalities and efficient separation heuristics even with complexity O(n).
To begin with, we investigate the separation problem for the rank 1 Chv$\acute{a}$tal-Gomory inequalities for the integer knapsack problem. First, we develop a dominant relation in the elementary closure for the knapsack problem. Then, we explicitly describe necessary conditions for an inequality to be a nondominated rank 1 Chv$\acute{a}$tal-Gomory inequality for the knapsack problem, which we call maximal inequality. Independently, we show that the separation problem can be seen as a series of combinatorial optimization problems. Finally, we show that the optimal solution of the separation problem also falls into the category of the maximal inequalities. The concept of a cover naturally arises in the description of the maximal inequalities. We develop a relationship between the traditional cover nequalities and maximal inequalities. Furthermore, the relationship is expanded to the integer knapsack problem. In short, cover inequalities belong to a subclass of maximal inequalities.
Next, we extend the results to the case of Chv$\acute{a}$tal-Gomory inequalities for multiple constraints with special structure. We explicitly describe a useful condition to find the most-violated rank 1 Chv$\acute{a}$tal-Gomory inequality for the generalized assignment problem. Then, we observe that the separation problem for the Chv$\acute{a}$tal-Gomory inequalities can be easily handled when the same coefficients appear repeatedly for the variables related to the same job. Motivated by the observation, we apply the result to bandwidth packing problem, which is a relaxation of integer multicommodity flow problem. Consequently, we suggest strong valid inequalities, called cutset inequalities,for bandwidth packing problem, derived from multiple constraints.
And finally, we study the Chv$\acute{a}$tal-Gomory inequalities for the capacitated network design problem. In the polyhedral analysis of arc capacity constraints, which appear in capacitated network design problem, the capacities of available facilities are oftenassumed to be divisible, i.e., they are integer multiples of each other. Furthermore, in most cases, at most three sorts of facilities are in consideration. To overcome the situation, we propose valid inequalities which can deal with multiple sorts of facilities with nondivisible capacities. We investigate the separation problem for the rank 1 Chv$\acute{a}$tal-Gomory inequalities for arc capacity constraints. As a result, we suggest a standard form of the most violated rank 1 Chv$\acute{a}$tal-Gomory inequality for arc capacity constraints. Furthermore, we show the relationship between Chv$\acute{a}$tal-Gomory inequalities and famous cutting planes for capacitated network design problem such as c-strong inequalities and cutset inequalities, which is a special case of the rank 1 Chv$\acute{a}$tal-Gomory inequalities for multiple constraints in the capacitated network design problem.
Computational experiments show that, with even simple separation heuristic, the lower bound is significantly improved and the overall performance of the cut-and-branch approach is significantly enhanced. Furthermore, as the separation procedure for the Chv$\acute{a}$tal-Gomory inequalities depend on integer arithmetics, it is basically numerically stable.
본 논문에서는 고모리 부등식의 특성과 이를 이용한 효율적인 절단평면의 생성방법에 대하여 다루고 있다. 1950년대 말 고모리 부등식의 발견은, 기존에 조합최적화 문제들을 다루는데 있어서 이산수학적 방법론이 대세를 이루던 환경을 현재 선형계획법에 기반한 해법이 이를 대체할 수 있도록 발전하는데 이론적인 토대를 마련해 준 연구이다. 고모리 부등식을 이용하면 선형계획법이라는 완화된 문제를 반복적으로 해결해 나감으로써 궁극적으로 정수해를 가지는 조합최적화 문제의 최적해를 구할 수 있다. 좀더 자세히 설명하면, 선형계획법의 최적해가 정수조건을 만족하지 못하면 이때 이러한 최적해를 제거해 줄 수 있는 고모리 부등식을 문제에 추가하여 다시 선형계획법을 최적화하는 방법을 반복함으로서 최종적으로는 정수특성을 갖는 최적해를 얻을 수 있다는 것이다. 이러한 방법론을 정수계획법적에서는 고모리 절단평면에 기반한 문제해결 기법이라고 한다.
고모리 부등식의 이러한 이론적 매력에도 불구하고 실제 1990년대 후반까지는 이를 실용적으로 사용하는 연구가 미진하였다. 그 이유는 고모리 부등식을 실제 생성하는 방식이 매우 간단하여 강력한 고모리 부등식을 생성하지 못하였으며, 이에 따라 문제해결 시간이 매우 길었기 때문이다. 그 대신에 각각의 문제의 특성을 고려한 절단평면을 생성하는 연구가 주류를 이루었다. 하지만 최근들어 수리계획법에 대한 사회적인 요구가 광범위하게 증대하고 이를 실질적으로 해결할 수 있는 방법론으로서 범용적이고 강력한 절단평면의 생성이 거의 유일한 실용적 해법으로 인식되면서 그 중요성이 다시 주목을 받게 되었다. 하지만 현재까지도 고모리 부등식과 같은 범용절단평면에 대한 실용적인 연구결과는 제한적인 것으로 보인다.
본 논문은 이러한 상황에서 강력한 고모리 부등식의 생성을 위한 연구를 수행하였다. 우선적으로 하나의 제약식을 가지는 배낭문제(Integer Knapsack Problem)에 대한 강력한 고모리 부등식의 특성을 정리하였으며, 이러한 특성을 이용하여 기존의 고모리 부등식의 생성과 같이 O(n) 시간을 사용하면서 매우 강력한 절단평면을 생성하는 방안은 개발하였다. 실증적인 비교를 위해 이를 일반적 할당문제(Generalized Assignment Problem)에 적용해 본 결과, 부등식의 생성시간은 지극히 짧으면서도 그 효율성은 할당문제 각각의 제약식에 배낭문제의 facet을 생성하는 절단평면기법과 비견될 정도의 결과를 얻을 수 있었다. 이것은 절단평면 생성방안에서 가장 중요한 요소인 시간과 효율성이라는 두 가지 목표를 모두 만족하는 것이라 할 수 있다. 또한 이번에 개발한 절단평면 개발방식은 기본적으로 정수연산에 기반한 것으로서 수치계산과 관련된 에러의 발생가능성을 확실히 줄인다는 것도 중요한 장점이다.
복수개의 제약식을 가지는 문제에 대한 고모리 부등식 생성방안에 대한 연구도 수행하였다. 그 결과 계수구조가 특별한 형식을 가지는 문제들에 대해서 강력한 고모리 부등식의 특성을 정리할 수 있었으며, 이를 실제 통신용량할당문제(Bandwidth Packing Problem)에 적용해 보았다. 그 결과 또한 매우 강력한 성능을 보이며 기존의 어려운 문제들에 대해서 만족할만한 성능을 보여주었다. 흥미있는 점은 이렇게 생성된 고모리 부등식이 기존에 통신망 설계문제(Capacitated Network Design Problem)와 관련해서 강력한 절단평면으로 알려진 cutset inequality 와 유사하는 것이었다. 이러한 동기로 본 논문에서는 통신망 설계문제와 관련한 고모리 부등식에 대해서도 연구를 진행하였다. 그 결과 기존에 통신망 설계문제와 관련해서 알려진 많은 부등식들이 고모리 부등식의 특수한 형태였음을 보일 수 있었다. 더불어 기존에 알려진 cutset inequality 들을 이론적으로 일반화 하였다.
고모리 부등식에 대한 본 논문의 연구결과는 고모리 부등식이 가지는 이론적인 장점을 실제 사용가능할 만큼 증진시켰다는데 의미가 있다고 할 수 있다. 하지만 그보다 더 주목해야 할 의미들이 있는 것으로 보인다. 이론적 측면에서는 본 연구결과를 일반적인 혼합정수계획법으로 확장하는 것이 매우 용이해 보인다. 실질적으로 본 논문의 연구결과는 기존에 혼합정수계획법에서 중요하게 사용하는 c-MIR 부등식과 매우 긴밀하게 연관되어져 있다. 또 하나의 의미는 쌍대문제(Dual Problem)와 관련된 정보를 절단평면 생성에 사용하는 방식에 대해 재조명 하였다는 것이다. 더불어 본 논문에 제안된 고모리 부등식 생성방식은 재귀적으로 사용하는 방식으로 더욱 강력한 고모리부등식을 생성하는 방식을 생각해 볼 수 있겠다. 이러한 방식은 이진정수계획문제 보다는 일반적인 정수변수를 가지는 문제들에 더욱 의미가 있을 것으로 보인다. 추가적으로, 실제 고모리 부등식을 상업적인 패키지에 사용할 수 있도록 추가적으로 실험을 더 실행해 보는 것도 의미가 있다고 할 수 있다. 궁극적으로는, 특별한 구조를 가지지 않는 일반적인 정수계획 문제에 대한 강력한 고모리 부등식 생성에 관한 단계적인 연구는 앞으로도 의미있는 과제가 될 것으로 생각된다.
