Intersection Cuts from Outer Polars of Truncated Cubes.

摘要

A truncated cube, by which is meant the convex hull of a subset of the vertices of the unit cube, has an outer polar whose facets are a subset of the facets of the octahedron (the outer polar of the cube). Procedures are discussed for generating valid truncations of the cube from the problem constraints, in the case of 0-1 integer programs, and for intersecting the halfines defined by the constraints that are tight for a basic solution to the linear program, with successive facets of the outer polars of these truncated cubes. The cutting planes obtained in this way are compared to other cuts.