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

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.

Article

Download

View PDF