Faces for linear inequalities in 0-1 variables
(1975) Mathematical Programming — Vol. 8, p. 165-178 (1975)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 545.5 KB
Details
- Authors
- 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. In 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.
- Affiliations
Citations
Wolsey, L. (1975). Faces for linear inequalities in 0-1 variables. Mathematical Programming, 8, 165-178. https://doi.org/10.1007/BF01580441 (Original work published 1975)