Studies on improving the convergence rate of the cutting plane methods

Abstract

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.