Implementing cutting plane management and selection techniques

One main objective of research in the area of mixed-integer programming is developing cutting plane techniques to improve the solvability of mixed-integer programs (MIPs). Various cutting plane separators are typically available in MIP solvers. The large number of cutting planes generated by these separators, however, can pose a computational problem. Therefore, a sophisticated cut management is indispensable. In this paper, we discuss cut quality measures and detail the architecture of the cut pool and the cut selection algorithm in the Mops (Mathematical OPtimization System) MIP solver. Furthermore, we analyze the impact that our algorithm has on the overall performance of the solver based on computational experiments. These experiments show that our algorithm succeeds in reducing the running times and the number of cutting planes added to the linear programming (LP) relaxation.

Citation

Technical Report, University of Paderborn, Warburger Str. 100, 33098 Paderborn, Germany, 12/2012

Article

Download

View Implementing cutting plane management and selection techniques