ISSN:
1436-4646
Keywords:
Integer Programming
;
Zero–One Programming
;
Facets
;
Valid Inequalities
;
Lifting
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We discuss a procedure to obtain facets and valid inequalities for the convex hull of the set of solutions to a general zero–one programming problem. Basically, facets and valid inequalities defined on lower dimensional subpolytopes are lifted into the space of the original problem. The procedure generalizes the previously known techniques for lifting facets in two respects. First, the general zero–one programming problem is considered rather than various special cases. Second, the procedure is exhaustive in the sense that it accounts for all the facets (valid inequalities) which are liftings of a given lower dimensional facet (valid inequality).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01609032
