Cutting plane methods, or delayed row generation methods, have been used successfully to solve mathematical programming problems with a large number of constraints. In this thesis, to improve the convergence of cutting plane methods, we propose new cutting plane methods for linear programming problems with many constraints and a new Benders decomposition algorithm for mixed integer programming problems.
The Benders decomposition algorithm is one of the cutting plane methods adopted to solve mixed integer programming problems. Yang and Lee proposed to use the feasibility cut closest to a solution in the set defined by all feasibility cuts to improve the convergence of the Benders decomposition algorithm. (Yang, Y. and Lee, J.M. A tighter cut generation strategy for acceleration of Benders decomposition. Computers & Chemical Engineering 44 (2012), 84-93) We propose a new cut selection scheme for the optimality cuts by extending the feasibility cut selection scheme proposed by Yang and Lee. We show that the optimality cuts generated by this scheme are Pareto-optimal. Furthermore, we develop a unified framework for generating the closest feasibility or optimality cut at the same time. Computational experiments on the multicommodity capacitated fixed charge network design problem demonstrate that the proposed algorithm improves the convergence speed and computational time.
Next, We consider Porumbel's cutting plane method. Porumbel introduced an accelerated cutting plane method for linear programming problems with many constraints using the intersection subproblem. (Porumbel, D. Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation. Mathematical Programming 155, 1-2 (2016), 147–197) However, the cutting plane method proposed by Porumbel has a drawback in that the origin must be a feasible solution to the linear programming problem. To overcome this drawback, we extend the intersection subproblem and propose a new cutting plane method based on the extended intersection subproblem. The computational results on the Steiner tree problem demonstrate that the proposed algorithm improves the number of iterations and the computational time.
Lastly, we consider the primal-dual column generation method, which solves the restricted master problem by using the primal-dual path following method. In this thesis, we propose a new primal-dual column generation method. The proposed method takes a dual interior point of the master problem, instead of a dual interior point of the restricted master problem, as the initial dual solution. Then, we obtain a dual solution by performing only one iteration of the primal-dual path following algorithm. Therefore, the proposed method may generate a violated dual constraint close to the initial dual solution. Additionally, since the proposed algorithm performs only one iteration of the primal-dual path following algorithm, the proposed algorithm overcomes the drawback of the primal-dual column generation method, which takes a lot of time to solve the restricted master problem. The computational experiments on the linear programming relaxation of the binpacking problems and the vehicle routing problem with time windows demonstrate the effectiveness of the proposed algorithm.
절단평면법(cutting plane method) 또는 행 생성 기법 (row generation method)은 제약식이 많은 수리계획법문제를 풀기 위한 방법으로 많이 사용되어 왔다. 이 학위논문에서는 제약식이 많은 선형계획법의 절단평면법과 벤더스 분할 알고리즘(Benders decomposition algorithm)의 수렴속도를 향상시키는 새로운 절단평면법을 제안한다.
먼저, 우리는 혼합정수계획법을 푸는 방법 중의 하나인 벤더스 분할 알고리즘의 성능향상 방법을 제안한다. Yang and Lee가 제안한 가능성 절단면(feasibility cut) 선택방법을 확장하여 새로운 최적성 절단면(optimality cut) 선택방법을 제안한다. (Yang, Y. and Lee, J.M. A tighter cut generation strategy for acceleration of Benders decomposition. Computers & Chemical Engineering 44 (2012), 84-93) 제안한 선택방법으로 생성된 최적성 절단면은 파레토 최적(Pareto-optimal)성질을 만족한다. 더 나아가, 제안한 최적성 절단면 선택 방법과 Yang and Lee가 제안한 가능성 절단면 선택방법을 동시에 고려한 벤더스 절단면(Benders cut) 선택방법을 제안한다. 제안한 방법을 네트워크 설계문제에 적용하여 제안한 벤더스 절단면의 선택방법의 효율성을 보인다.
다음으로, 우리는 Porumbel이 제안한 절단평면법에 대해 살펴보고, 이 방법의 한계점을 알아본다. (Porumbel, D. Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation. Mathematical Programming 155, 1-2 (2016), 147–197) Porumbel의 절단평면법은 교차부문제(intersection subproblem)를 이용하여 절단평면법의 성능을 향상시켰다. 하지만 Porumbel이 제안한 절단평면법은 원점이 실행가능 해인 선형계획법에만 적용할 수 있는 단점을 가지고 있다. 이러한 단점을 극복하기 위해, 우리는 기존의 교차부문제를 확장하며, 확장된 교차부문제를 이용한 새로운 절단평면법을 제안한다. 제안한 문제를 스타이너트리 문제(Steiner tree problem)에 적용하여 제안된 알고리즘의 반복횟수와 문제를 푸는 시간이 개선됨을 보인다.
마지막으로, 우리는 원쌍대열생성기법(primal-dual column generation method)의 수렴속도를 향상시키기 위해 새로운 원쌍대열생성기법을 제안한다. 기존의 원쌍대열생성기법은 완화된 쌍대문제의 내부점을 초기쌍대해로 정한 후, 원쌍대내부알고리즘(priaml-dual path following algorithm)을 이용하여 완화된 쌍대문제의 최적의 솔루션에 가까운 쌍대해를 구한다. 제안한 알고리즘은 완화된 쌍대문제의 내부점을 초기해로 정하는 대신 쌍대문제의 내부점을 초기해로 정한다. 또한 초기해로부터 원쌍대내부점알고리즘을 한번의 실행횟수만 진행하여 쌍대해를 구한다. 제안한 알고리즘은 초기쌍대해에 가까운 쌍대제약식을 찾을 수 있어 원쌍대열생성기법의 실행횟수가 줄어들며, 원쌍대내부점알고리즘의 한번의 실행횟수만 진행하기 때문에 주문제를 푸는데 많은 시간이 소요되는 원쌍대열생성기법의 단점을 개선한다. 상자채우기문제(bin packing problem)와 시간제약이 있는 차량문제(vehicle routing problems with time windows)를 통하여 제안한 알고리즘의 성능을 보인다.
