Implementing cutting plane management and selection techniques

Franz Wesselmann(wesselmanndsor.de)
U. H. Suhl(uwe.suhlfu-berlin.de)

Abstract: 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.

Keywords: integer programming, cutting planes

Category 1: Integer Programming (Cutting Plane Approaches )

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

Download: [PDF]

Entry Submitted: 12/21/2012
Entry Accepted: 12/21/2012
Entry Last Modified: 12/21/2012

Modify/Update this entry