Faces for a linear inequality in 0–1 variables

Special subclasses of inequalities for which all faces can be generated are demonstrated, including the “matroidal” and “graphic” inequalities, where a count on the number of such inequalities is obtained, and inequalities where all Faces can be derived from lower dimensional faces.

Abstract

Given a linear inequality in 0–1 variables we attempt to obtain the faces of the integer hull of 0–1 feasible solutions. For the given inequality we specify how faces of a variety of lower-dimensional inequalities can be raised to give full-dimensional faces. In terms of a set, called a ldquostrong coverrdquo, we obtain necessary and sufficient conditions for any inequality with 0–1 coefficients to be a face, and characterize different forms that the integer hull must take.\nIn general the suggested procedures fail to produce the complete integer hull. Special subclasses of inequalities for which all faces can be generated are demonstrated. These include the ldquomatroidalrdquo and ldquographicrdquo inequalities, where a count on the number of such inequalities is obtained, and inequalities where all faces can be derived from lower dimensional faces.