Studies on the properties of the cut-generating linear program and separation of general-purpose cuts

Abstract

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.