Cutting planes (cuts) are important in solving general mixed-integer linear programs (MILPs) by the branch-and-cut algorithm. In particular, it has been experimentally shown that the iterative generation of general-purpose cuts plays a major role in improving the performance of the branch-and-cut algorithm recently. General-purpose cuts are valid inequalities that can be derived from a given mathematical formulation, regardless of the type of MILPs. In this thesis, we study the properties of the cut-generating linear program that generates general-purpose cuts and propose several cut generation methods using them.
First, we introduce the membership linear program (MLP) which was used by Bonami and propose its practical implementation methods. The MLP is the dual problem of a simplified version of the cut-generating linear program. This problem enables fast and iterative cut generation since it has a similar structure to the original LP relaxation of an MILP. We introduce the relationship between general-purpose cuts which are generated by solving the MLP and propose a simple cut strengthening method. We also derive the MLP for general MILPs that include inequality constraints and bounded variables, and introduce a method for constructing the simplex tableau of the original LP relaxation. Consequently, our cut generation algorithm can be implemented regardless of the type of MILPs and the test environment.
Second, we introduce a method of split cut generation by applying general split disjunction to the MLP. In addition to the existing lift-and-project cuts generated by applying elementary disjunction, we show how well the generation of additional split cuts can approximate the optimal value of a given MILP. We study the properties of the MLP with general split disjunction and examine the improvement due to the use of split cuts with disjunctions having small L1-norm. The computational results using benchmark MILP instances show the effect of split cuts using disjunctions with small L1-norm.
Third, we propose an overall general-purpose cut generation and selection method to improve the performance of the branch-and-cut algorithm. Based on the MLP, we develop an integrated rank-1 split cut generation algorithm. Our algorithm generates lift-and-project cuts, split cuts, and reduce-and-split cuts from the simplex tableau which is constructed by the reduced costs of the MLP. We also extend the existing reduce-and-split method and apply it to our algorithm. Next, we propose a cut selection method to limit the number of cuts that are added to the original LP relaxation. Since we need to solve the LP relaxation of a given MILP repeatedly with the cuts added, it can be difficult to solve the LP relaxation if all generated cuts are added. Through quality measures and adopting a cut pool, cuts to be added to the original LP relaxation are selected. We finally show experimental results on MILPs with the added cuts which are solved by the branch-and-cut algorithm.
절단면은 일반적인 혼합정수계획법 문제를 분지절단법으로 해결하기 위해 필요한 핵심적인 요소이다. 특히 최근들어 범용 절단면의 반복적인 생성이 분지절단법의 성능을 결정하는데 가장 큰 역할을 한다는 것이 실험적으로 밝혀졌다. 범용 절단면은 혼합정수계획법 문제의 형태에 상관없이, 주어진 수리 모형으로부터 유도할 수 있는 유효 부등식이다. 본 논문에서는 범용 절단면을 생성하는 절단면 생성 문제의 특성을 연구하고 이를 이용하여 다양한 범용 절단면을 생성하는 방법을 제안한다.
첫 번째로, 범용 절단면의 효율적인 생성을 위해 Bonami가 제안한 소속 문제 (membership linear program)를 소개하고 이것의 실제 구현 방법을 제안한다. 소속 문제는 단순화된 절단면 생성 문제의 쌍대문제로, 선형계획법으로 완화된 원 문제의 형태와 유사하기 때문에 빠르고 반복적인 절단면 생성을 가능하게 한다. 이 문제를 풀어 생성가능한 범용 절단면의 종류 및 서로의 관계를 소개하고, 이 관계를 이용하여 간단한 절단면 강화 방법을 제안한다. 또한 부등식 제약 조건 및 유한 변수가 포함된 혼합정수계획법 문제에 대한 소속 문제를 유도하고, 선형계획법으로 완화된 원 문제의 심플렉스표 (simplex tableau) 구성 방법을 소개한다. 이를 이용하여 원 문제의 형태 및 실험 환경에 상관없이 범용 절단면 생성 알고리즘을 구현 할 수 있다.
두 번째로, 소속 문제에 일반 논리합 (general disjunction)을 적용하여 분할 절단면 (split cut)을 생성하는 방법을 소개한다. 기본 논리합 (elementary disjunction)을 적용하여 생성되는 기존의 올림 및 투영 절단면 (lift-and-project cut)에 더하여, 추가적인 분할 절단면의 생성이 원 문제의 최적 값을 얼마나 잘 근사할 수 있는지 확인한다. 또한 일반 논리합이 적용된 소속 문제의 특성을 연구하고 논리합의 L1-norm 값에 따라 다르게 생성되는 분할 절단면의 성능을 비교한다. 다양한 혼합정수계획법 예시 문제들을 이용한 실험을 통해서 L1-norm 값이 작은 일반 논리합으로부터 생성되는 분할 절단면의 효과를 확인하였다.
마지막으로, 분지절단법의 성능 향상을 위한 종합적인 범용 절단면 생성 및 선택 방법을 제안한다. 소속 문제를 기반으로 여러 강력한 범용 절단면의 통합 생성 알고리즘을 개발한다. 이 알고리즘은 올림 및 투영 절단면과 분할 절단면, 그리고 축소 및 분할 절단면 (reduce-and-split cut)을 소속 문제의 수정비용 (reduced cost)으로 구성된 심플렉스표에서 생성한다. 또한 기존의 축소 및 분할 방법 (reduce-and-split method) 을 확장하여 본 알고리즘에 적용한다. 다음으로, 원 문제에 추가되는 절단면의 개수를 제한하기 위한 절단면 선택 방법을 제안한다. 분지절단법은 선형계획법으로 완화된 원 문제를 반복적으로 풀어야 하기 때문에 생성된 모든 절단면을 사용하면 오히려 문제 해결이 더 어려워 질 수 있다. 절단면 풀 (cut pool) 및 생성된 절단면의 성능 평가를 통하여 원 문제에 추가될 절단면을 선택한다. 실험적으로 절단면이 추가된 원 문제를 분지절단법으로 풀었을 때의 결과를 확인하였다.
