Search and Cut: New Class of Cutting Planes for 0-1 Programming

Osman Oguz (ooguzbilkent.edu.tr)

Abstract: The basic principle of the cutting plane techniques is to chop away the portions of the solution space of the linear programming relaxation of an integer program that contain no integer solutions. this is true for both Gomory's cutting planes, and other more recent cuts based on valid inequalities. Obtaining a partial or full description of the convex hull of the set of integer solutions is the underlying motivation for these approaches. The cuts proposed in this study break away from this motivation, and allow for the chopped away portions of the solution space to have both feasible and infeasible integer points.

Keywords: 0-1 Integer Programming, Cutting Planes, Branch and Cut

Category 1: Integer Programming (0-1 Programming )

Citation:

Download: [Postscript]

Entry Submitted: 05/30/2002
Entry Accepted: 05/30/2002
Entry Last Modified: 05/30/2002

Modify/Update this entry